代码随想录|图论|06岛屿数量（广搜BFS）

BFS版本

代码随想录|图论|05岛屿数量（深搜DFS）-CSDN博客

现在换成DFS来写，dfs的作用还是对当前点的四周进行标记！

#include <bits/stdc++.h>
using namespace std;

// 定义四个方向
int dir[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};

void bfs(vector<vector<int>> &grid, vector<vector<bool>> &visited, int x, int y)
{
    // 队列里面的是已经走过的节点
    queue<pair<int, int>> q;
    q.push({x, y});
    visited[x][y] = true;   // 只要加入队列，立刻标记
    // 直到队列为空，说明所有的点都被遍历了
    while (!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();
        int curx = cur.first;
        int cury = cur.second;
        for (int i = 0; i < 4; i++)
        {
            int nextx = curx + dir[i][0];
            int nexty = cury + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size())
                continue;
            if (grid[nextx][nexty] == 1 && !visited[nextx][nexty])
            {
                q.push({nextx, nexty});
                visited[nextx][nexty] = true;   // 只要加入队列，立刻标记
            }
        }
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m, 0));
    vector<vector<bool>> visited(n, vector<bool>(m, false));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> grid[i][j];
        }
    }
    int result = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (grid[i][j] == 1 && !visited[i][j])
            {
                result++;
                bfs(grid, visited, i, j);
            }
        }
    }
    cout << result << endl;
    return 0;
}