DFS与BFS专题

99. 岛屿数量

讲解：https://programmercarl.com/kamacoder/0099.岛屿的数量广搜.html#思路
DFS代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 55;

int n, m;
int g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int sx, int sy)
{
    for (int i = 0; i < 4; i++)
    {
        int a = sx + dx[i], b = sy + dy[i];
        if (a < 0 || a >= n || b < 0 || b >= m) continue;
        if (st[a][b] || g[a][b] == 0) continue;
        st[a][b] = true;
        dfs(a, b);
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!st[i][j] && g[i][j] == 1)
            {
                st[i][j] = true;
                res++;
                dfs(i, j);
            }
        }
    }
    cout << res << endl;
    return 0;
}

BFS代码

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 55;

int n, m;
int g[N][N];
bool st[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs(int sx, int sy)
{
    queue<PII> q;
    q.push({sx, sy});
    st[sx][sy] = true;

    while (q.size())
    {
        PII t = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int a = t.first + dx[i], b = t.second + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (st[a][b] || g[a][b] == 0) continue;
            q.push({a, b});
            st[a][b] = true;
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> g[i][j];

    int res = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (!st[i][j] && g[i][j] == 1)
            {
                res++;
                bfs(i, j);
            }
        }
    }
    cout << res << endl;
    return 0;
}