一本通-1335：【例2-4】连通块（DFS泛洪算法）

【题目描述】 一个n * m的方格图，一些格子被涂成了黑色，在方格图中被标为1，白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子能通过四连通的走法（上下左右），只走黑色格子，到达该联通块中的其它黑色格子。

【输入】 第一行两个整数n,m(1≤n,m≤100)，表示一个n * m的方格图。

接下来n行，每行m个整数，分别为0或1，表示这个格子是黑色还是白色。

【输出】 一行一个整数ans，表示图中有ans个黑色格子连通块。

【输入样例】 3 3 1 1 1 0 1 0 1 0 1

【输出样例】 3

---

#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > grid(105, vector<int>(105));
int n, m;
int direction[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

void DFS(int row, int col)
{
    grid[row][col] = 0;
    for (int i = 0; i < 4; ++i) {
        int nextRow = row + direction[i][0];
        int nextCol = col + direction[i][1];
        if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && grid[nextRow][nextCol] == 1) {
            DFS(nextRow, nextCol);
        }
    }
}


int solve()
{
    int cnt = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1) {
                ++cnt;
                DFS(i, j);
            }
        }
    }

    return cnt;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    cout << solve() << endl;

    return 0;
}