一本通-1329：【例8.2】细胞（DFS和BFS两种解法）

【题目描述】 一矩形阵列由数字00到99组成,数字11到99代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数。如下阵列，有44个细胞：

4 10 0234500067 1034560500 2045600671 0000000089

【输入】 第一行为矩阵的行n和列m;

下面为一个n×m的矩阵。

【输出】 细胞个数。

【输入样例】 4 10 0234500067 1034560500 2045600671 0000000089

【输出样例】

4

---

如果不限定方法的化，很明显的泛洪算法，用DFS来求解。

当然也可以用BFS来求解。

首先看DFS的方法：

#include <bits/stdc++.h>

using namespace std;

int m, n;
vector<vector<int> > grid(1005, vector<int>(1005));
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]) {
            DFS(nextRow, nextCol);
        }
    }
}


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

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

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

    cout << cnt << endl;

    return 0;
}

BFS的思路是将起始点上下左右的临近细胞入队。

 #include <bits/stdc++.h>

using namespace std;

struct Node
{
    int row, col;
    Node(int x, int y): row(x), col(y) {}
};

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

void BFS(int row, int col)
{
    queue<Node> q;
    grid[row][col] = 0;
    q.push(Node(row, col));
    while (!q.empty()) {
        Node tmp = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int nextRow = tmp.row + direction[i][0];
            int nextCol = tmp.col + direction[i][1];
            if (0 <= nextRow && nextRow < m && 0 <= nextCol && nextCol < n && grid[nextRow][nextCol]) {
                grid[nextRow][nextCol] = 0;
                q.push(Node(nextRow, nextCol));
            }
        }
    }
}


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

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

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

    cout << cnt << endl;

    return 0;
}