鼎言代码修改

Algor

2025-11-29 15:56:02

发布于：广东

1阅读

0回复

0点赞

这份代码的问题比前两份“隐蔽”一点，不过核心有几个关键点：

先说整体思路

你现在的想法是：

对每个还没访问过的格子做一次 dfs(i, j)，判断这个连通块是不是“封闭”的。
dfs 里如果在搜索过程中碰到了“外围一圈”（坐标为 0 或 n+1），就返回 false，说明这个连通块是“漏到外面”的。
用 flgs 标记当前连通块中的点，如果 dfs 返回 true，就把这些点改成 2。

这个思路本身是可行的，但实现上有几个致命细节问题。

❌ 问题 1：对所有格子都 dfs，包括值为 1 的格子

外层枚举是：

for(int i = 1;i <= n;i++){
    for(int j = 1;j <= n;j++){
        if(!vis[i][j]){
            bool f = dfs(i,j);
            ...
        }
    }
}

这里没有判断 g[i][j] 是不是 0，也就是说：

值为 1 的格子也会被当作连通块的起点。
进入 dfs 后，你只禁止了继续走到 g[x][y] == 1 的邻居：
```
if(g[x][y]==1 || vis[x][y])continue;
```
但是从 1 出发，可以走到周围的 0（因为起点处没有检查 g[sx][sy] 的值）。

这会导致一个很严重的问题：

本来应该只通过“0 相邻”来判断连通块是否能到外面，现在变成通过“0 和 1 混一起”的连通关系来判断。

举个典型情况：

一圈 1 把一团 0 围起来（这是要涂成 2 的区域）。
这圈 1 里面的某个 1，会和内部的 0 相邻，同时和外部的 0 也相邻。

你的代码从这个 1 开始 dfs 时，会：

从这个 1 走进内部那片 0（因为 0 可以走）。
又从这个 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 之间的连通。

修复方式之一：外层这样写：

if (!vis[i][j] && g[i][j] == 0) {
    bool f = dfs(i, j);
    ...
}

同时，dfs 里也可以直接假设 g[sx][sy] == 0 成立。

❌ 问题 2：起点格子根本没有标记到 `flgs` 中

在 dfs 里，你写的是：

vis[sx][sy]=1;
for(auto i : th){
    int x = sx + i.first,y = i.second + sy;
    ...
    if(g[x][y]==1 || vis[x][y])continue;
    flgs[x][y]=1;
    bool f = dfs(x,y);
    ...
}

你只对“邻居”标记了 flgs[x][y] = 1，起点 (sx, sy) 从来没进 flgs。

外层如果认为这个连通块是封闭的：

if(f){
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            if(flgs[i][j])g[i][j]=2;
        }
    }
}

那这次 DFS 的“起点格子”即使是 0，也不会被改成 2。
所以每个被填充的连通块，都会漏掉一个格子（第一次 DFS 进入的那个 0）。

正确做法是：一进入 DFS，就把当前点计入 flgs，前提是它是 0：

bool dfs(int sx,int sy){
    vis[sx][sy] = 1;
    flgs[sx][sy] = 1;    // 这里要加上

    bool ok = true;
    for (auto d : th) {
        int x = sx + d.first, y = sy + d.second;
        ...
    }
    return ok;
}

✅ 怎么改比较稳妥？

在你这个写法的基础上，改成下面这种比较安全：

bool dfs(int sx, int sy) {
    vis[sx][sy] = 1;
    flgs[sx][sy] = 1;   // 当前点属于本连通块

    bool closed = true; // 假设当前连通块是封闭的

    for (auto d : th) {
        int x = sx + d.first;
        int y = sy + d.second;

        // 走到“外圈”（0 或 n+1）说明能连到外部
        if (x == 0 || x == n+1 || y == 0 || y == n+1) {
            closed = false;
            continue;   // 不用继续往外走了
        }

        // 只在 1..n 范围内访问
        // 只考虑 0；1 当作墙
        if (g[x][y] != 0 || vis[x][y]) continue;

        if (!dfs(x, y)) closed = false;
    }

    return closed;
}

外层循环改成：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (!vis[i][j] && g[i][j] == 0) {  // 只从 0 开始 dfs
            bool f = dfs(i, j);
            if (f) {
                for (int x = 1; x <= n; x++) {
                    for (int y = 1; y <= n; y++) {
                        if (flgs[x][y]) g[x][y] = 2;
                    }
                }
            }
            // 重置 flgs
            flgs = vector<vector<bool>>(44, vector<bool>(44, false));
        }
    }
}