DFS深度优先搜索访问数据不懂

Question

为什么说DFS不会访问到闭合圈的0，为什么闭合圈的0不会跟边界0一样被标记为1，DFS在题目所给数据的数组中是怎么进行搜索访问的

Answer 1

引自免费微信小程序：皆我百晓生

为了理解为什么深度优先搜索（DFS）在这个特定的问题中不会访问到闭合圈内部的0，以及为什么闭合圈内部的0不会被标记为1，让我们深入分析一下DFS的工作原理，并结合给定问题的具体条件。

DFS算法原理

DFS是一种用于遍历或搜索树或图的算法。它从根节点开始，尽可能深的搜索树的分支。如果到达了一个叶子节点（在本题中，即边界或闭合圈），它会回溯，然后继续探索下一个分支。DFS通常使用递归实现，或通过使用栈手动实现。

题目背景

在这个问题中，我们有一个由0和1组成的n×n方阵，其中1构成了一个闭合圈，而闭合圈内部有至少一个0。目标是将闭合圈内部的所有0替换为2。

解释为什么DFS不会访问闭合圈内的0

关键点在于闭合圈的定义和DFS的遍历方式。闭合圈意味着从闭合圈内部的任何0出发，都无法通过仅经过其他0的路径到达边界。因此，当从边界或闭合圈外部的任意0开始进行DFS时，算法会一直沿着可达的路径前进，直到遇到边界或闭合圈的边缘（即1）。一旦遇到这些障碍，DFS就会回溯并尝试其他路径。但是，由于闭合圈内部的0与边界不可达，DFS将永远不会进入闭合圈内部，从而不会标记这些0。

如何确保闭合圈内的0被正确识别

为了解决这个问题，我们需要从边界开始进行DFS，将所有与边界相连的0标记为1（或任何非0非2的值）。这样，闭合圈内部的0将保持不变。之后，再次遍历整个方阵，将所有剩余的0（即那些没有被DFS标记的0）替换为2。这是因为它们只能是闭合圈内部的0，因为所有与边界相连的0已经被标记了。

完整代码示例

下面是一个修改后的代码示例，展示如何实现上述逻辑：

#include <iostream>
using namespace std;

const int MAXN = 32;
int a[MAXN][MAXN], b[MAXN][MAXN];
int dx[5] = {0, -1, 1, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};
int n;

void dfs(int p, int q) {
    if (p < 0 || p > n || q < 0 || q > n || a[p][q] != 0) return;
    a[p][q] = 1; // Mark as visited
    for (int i = 1; i <= 4; i++) {
        dfs(p + dx[i], q + dy[i]);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> b[i][j];
            a[i][j] = (b[i][j] == 1) ? 2 : 0; // Mark walls as 2 and empty cells as 0
        }
    }

    // Perform DFS from all boundary cells to mark all cells reachable from the boundary
    for (int i = 0; i <= n + 1; i++) {
        dfs(i, 0); dfs(i, n + 1);
        dfs(0, i); dfs(n + 1, i);
    }

    // Convert remaining 0s (those not reachable from the boundary) to 2
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i][j] == 0) {
                cout << 2 << ' ';
            } else {
                cout << b[i][j] << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
}

这段代码首先通过从所有边界细胞开始的DFS来标记所有与边界相连的0。然后，它遍历整个方阵，将所有未被标记的0（即闭合圈内部的0）转换为2。这样，我们就能确保只有闭合圈内部的0被转换，而所有其他0都被正确处理。