代码随想录算法训练营 Day51 图论Ⅱ岛屿问题Ⅰ

图论

题目

99. 岛屿数量
使用 DFS 实现方法
判断岛屿方法
1. 遍历图，若遍历到了陆地 grid[i][j] = 1 并且陆地没有被访问，在这个陆地的基础上进行 DFS 方法，或者是 BFS 方法
2. 对陆地进行 DFS 的时候时刻注意以访问的元素添加访问标记

// DFS方法1
#include <iostream>
#include <vector>

int dir[4][2] = {0,1,1,0,-1,0,0,-1};
void dfs(std::vector<std::vector<int>>& grid, std::vector<std::vector<bool>>& vis, int x, int y) {
    // 从四个方向进行搜索
    for (int i = 0; i < 4; ++i) {
        int nexti = x + dir[i][0];
        int nextj = y + dir[i][1];
        // 边界情况判定
        if (nexti < 0 || nexti >= grid.size()
         || nextj < 0 || nextj >= grid[0].size()) continue;
        // 访问情况判定
        if (!vis[nexti][nextj] && grid[nexti][nextj] == 1) {
            // 时刻注意访问标记
            vis[nexti][nextj] = true;
            dfs(grid, vis, nexti, nextj);
        }
    }
}

int main() {
    // 输入处理
    int n, m, res = 0;
    std::cin >> n >> m;
    std::vector<std::vector<int>> grid(n, std::vector<int>(m, 0));
    std::vector<std::vector<bool>> vis(n, std::vector<bool>(m, false));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> grid[i][j];
        }
    }
    // 遍历网格进行DFS操作
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            // 访问到新陆地对该陆地进行遍历
            if (grid[i][j] == 1 && !vis[i][j]) {
                res++; // 记录新大陆
                vis[i][j] = true;
                dfs(grid, vis, i, j);
            }
        }
    }

    // 输出处理
    std::cout << res << std::endl;
}


// dfs 三部曲写法
#include <iostream>
#include <vector>
using namespace std;

int dir[4][2] = {0,-1,-1,0,1,0,0,1}; // 逆时针顺序
// 第一步参数与返回值
void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    // 第二部 终止条件
    if (vis[x][y] || grid[x][y] == 0) return;
    // 第三部 单层递归逻辑
    vis[x][y] = true;
    for (int i = 0; i < 4; ++i) {
        int nextX = x + dir[i][0];
        int nextY = y + dir[i][1];
        if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
        dfs(grid, vis, nextX, nextY);
    }
}

int main() {
    int n, m, res = 0;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!vis[i][j] && grid[i][j] == 1) {
                res++;
                dfs(grid, vis, i, j);
            }
        }
    }

    cout << res << endl;
}

使用广度优先搜索方法
主函数部分不变，调用变成广度优先搜索
广度优先搜索保证入队列的时候就对数据做标记为访问
如果在取出队列时候标记会导致大量重复元素入队！

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int dir[4][2] = {0,-1,-1,0,1,0,0,1};
void bfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    // 创建队列存储下标
    queue<pair<int, int>> que;
    // 保证入队的时候就标记访问防止重复访问
    que.push(make_pair(x, y));
    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.first + dir[i][0];
            int nextY = cur.second + dir[i][1];
            if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
            if (!vis[nextX][nextY] && grid[nextX][nextY] == 1) {
                que.push({nextX, nextY});
                vis[nextX][nextY] = true; // 入队即标记防止重复
            }
        }
    }
}

int main() {
    int n, m, res = 0;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!vis[i][j] && grid[i][j] == 1) {
                res++;
                bfs(grid, vis, i, j);
            }
        }
    }

    cout << res << endl;
}

100. 岛屿的最大面积
岛屿最大面积，给出广度优先搜索，深度优先搜索（A 和 B）
深度优先 B广度优先在函数外初始化记录，深度优先 A 在函数内初始化记录

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int tmp = 0;
int dir[4][2] = {0,-1,-1,0,1,0,0,1};

int bfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    tmp = 1;
    queue<pair<int, int>> que;
    que.push(make_pair(x, y));
    vis[x][y] = true;
    while (!que.empty()) {
        pair<int, int> cur = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            int nextX = cur.first + dir[i][0];
            int nextY = cur.second + dir[i][1];
            if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
            if (!vis[nextX][nextY] && grid[nextX][nextY] == 1) {
                tmp++;
                que.push({nextX, nextY});
                vis[nextX][nextY] = true;
            }
        }
    }
    return tmp;
}

void dfs(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    // 1 fin
    if (vis[x][y] || grid[x][y] == 0) return;
    vis[x][y] = true;
    tmp++;
    for (int i = 0; i < 4; ++i) {
        int nextX = x + dir[i][0];
        int nextY = y + dir[i][1];
        if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY >= grid[0].size()) continue;
        dfs(grid, vis, nextX, nextY);
    }
}

void dfs2(vector<vector<int>>& grid, vector<vector<bool>>& vis, int x, int y) {
    // 2
    for (int i = 0; i < 4; ++i) {
        int nextX = x + dir[i][0];
        int nextY = y + dir[i][1];
        if (nextX < 0 || nextX >= grid.size() || nextY < 0 || nextY > grid[0].size()) continue;
        if (!vis[nextX][nextY] && grid[nextX][nextY] == 1) {
            tmp++;
            vis[nextX][nextY] = true;
            dfs2(grid, vis, nextX, nextY);
        }
    }
}


int main(){
    int n, m, res = 0, maxV = 0;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> vis(n, vector<bool>(m, false));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> grid[i][j];
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!vis[i][j] && grid[i][j] == 1) {
                res++;
                // 深度优先 1
                // tmp = 0; // 因为dfs内首先计算tmp
                // dfs(grid, vis, i, j);
                // maxV = max(maxV, tmp);
                // 深度优先 2
                tmp = 1; // dfs需要初始
                vis[i][j] = true;
                dfs2(grid, vis, i, j);
                maxV = max(maxV, tmp);
                // 广度优先
                // maxV = max(maxV, bfs(grid, vis, i, j));
            }
        }
    }
    // cout << "res" << res << endl;
    cout << maxV << endl;
    return 0;
}