本文共 1442 字，大约阅读时间需要 4 分钟。

DFS 是解决这道题的好方法，因为它简单且适合处理这种寻找连通区域的问题。我们可以通过遍历矩阵，找到不是 '0' 的点，然后从这些点开始进行 DFS，检查四个方向（上、下、左、右）是否有相连的非 '0' 数字。如果有，就将这个点标记为 '0'，并继续深入查找。每次启动 DFS，就意味着发现了一个新的细胞，因此 ans 会加 1。

步骤说明

代码实现

#include 
   
    
#include 
    
     
using namespace std;
int n, m, ans;
char a[105][105];
int dx[5] = {0, -1, 1, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};
void dfs(int x, int y) {
    for (int i = 1; i <= 4; ++i) {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (xx > 0 && xx <= n && yy > 0 && yy <= m && a[xx][yy] != '0') {
            a[xx][yy] = '0';
            dfs(xx, yy);
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i][j] != '0') {
                dfs(i, j);
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
    
   

代码解释

• 读取输入：使用 cin 读取输入数据，并将每一行的字符存储在二维数组 a 中。
• DFS 函数：定义了一个递归函数 dfs，用于从给定位置开始检查四个方向的邻居。如果邻居在矩阵范围内且不是 '0'，则标记它并继续递归。
• 遍历矩阵：在主函数中，遍历矩阵中的每一个位置。如果位置的值不是 '0'，启动一次 DFS，并将 ans 加 1。
• 输出结果：最后输出 ans 的值，即矩阵中的细胞个数。

这种方法通过封路（标记为 '0'）确保每个细胞只被计算一次，能够高效地解决问题。

转载地址：http://fdim.baihongyu.com/