这份代码的问题比前两份“隐蔽”一点,不过核心有几个关键点:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
先说整体思路
你现在的想法是:
1. 对每个还没访问过的格子做一次 dfs(i, j),判断这个连通块是不是“封闭”的。
2. dfs 里如果在搜索过程中碰到了“外围一圈”(坐标为 0 或 n+1),就返回 false,说明这个连通块是“漏到外面”的。
3. 用 flgs 标记当前连通块中的点,如果 dfs 返回 true,就把这些点改成 2。
这个思路本身是可行的,但实现上有几个致命细节问题。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
❌ 问题 1:对所有格子都 DFS,包括值为 1 的格子
外层枚举是:
这里没有判断 g[i][j] 是不是 0,也就是说:
* 值为 1 的格子也会被当作连通块的起点。
* 进入 dfs 后,你只禁止了继续走到 g[x][y] == 1 的邻居:
但是从 1 出发,可以走到周围的 0(因为起点处没有检查 g[sx][sy] 的值)。
这会导致一个很严重的问题:
> 本来应该只通过“0 相邻”来判断连通块是否能到外面,现在变成通过“0 和 1 混一起”的连通关系来判断。
举个典型情况:
* 一圈 1 把一团 0 围起来(这是要涂成 2 的区域)。
* 这圈 1 里面的某个 1,会和内部的 0 相邻,同时和外部的 0 也相邻。
你的代码从这个 1 开始 dfs 时,会:
1. 从这个 1 走进内部那片 0(因为 0 可以走)。
2. 又从这个 1 走到外面的 0(因为也是 0),再一路走到边界 x==0 或 y==0,于是 return false。
结果:
* 内部那片本来“封闭”的 0,在这次 DFS 里被访问到了(vis=1),但因为整个 DFS 返回了 false,你不会把它们设为 2。
* 之后外层循环再也不会从这些内部 0 起点调用 DFS(因为 vis 已经是 1),它们被“判死刑”,永远保持 0,不会被涂成 2。
👉 结论:
DFS 不应该从值为 1 的格子开始,只应该从 0 开始。
连通性的判断应该只看 0 与 0 之间的连通。
修复方式之一:外层这样写:
同时,dfs 里也可以直接假设 g[sx][sy] == 0 成立。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
❌ 问题 2:起点格子根本没有标记到 FLGS 中
在 dfs 里,你写的是:
你只对“邻居”标记了 flgs[x][y] = 1,起点 (sx, sy) 从来没进 flgs。
外层如果认为这个连通块是封闭的:
那这次 DFS 的“起点格子”即使是 0,也不会被改成 2。
所以每个被填充的连通块,都会漏掉一个格子(第一次 DFS 进入的那个 0)。
正确做法是:一进入 DFS,就把当前点计入 flgs,前提是它是 0:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
✅ 怎么改比较稳妥?
在你这个写法的基础上,改成下面这种比较安全:
外层循环改成:
这样:
1. 只搜索 0 的连通块;
2. 起点也会被正确标记并填成 2;
3. 能碰到外围一圈(0 / n+1)的块会被判断为“非封闭”,不填色。