题解 P1451 【求细胞数量】

Thomas_Cat · 2020-10-16 23:09:05 · 题解

这题其实用 bfs 不好做，最好做的方法是最简单易懂的 dfs 。

首先，我们先来分析一下题目：

• 要找到细胞块，当一个细胞块被 0 围住 的时候，这个就算是一个细胞块。

• 细胞块只能是 上下左右 ，斜角是无用的。

• 当你使用 dfs 的时候，注意判断使用的边界是不是 当 Map_{i,j} 的时候 1 \le i \le n, 1 \le j \le m 。

那么我们直接来看一下图（关于模拟和查找下一步是不是 细胞块 的。

注：上图中使用的 Map(i,j) 正规写法应该是 Map_{i,j} ，但是这里为了贴近代码的数组就没有使用正规写法

显然，我们只用开一个数组 X_i , Y_i 来记录他们的变化规律 （注意 X_0 , Y_0 是 0）：

int X[5] = { 0,-1,0,1,0 };
int Y[5] = { 0,0,-1,0,1 };

之后，我们来看一个例子：

如果我从 Map_{1,1} 开始遍历的话，就会做很多的无用功，为什么呢？因为 Map_{1,1} 开始遍历可能就不是遍历到所有 > 0 的点了，会遍历到 0 ，所以会做很多的无用功。

因此我们在 dfs 前先加入一个判断：

or (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (Map[i][j] != '0' && flag[i][j] == 0) {//如果这个点是细胞并且没有被访问过
                dfs(i, j, ++sum);//dfs
            }
        }

加下来也就没有什么好说的了，注意这里我的代码的 init() 函数是用来控制输入输出的，这样看起来可以简洁明了一些。

总体的代码（无注释）如下：