超级详细题解：矩阵中的连通区域标记（BF

1. 题目描述
   给定一个 n × n 的矩阵，其中：

0 表示可以通行的区域

1 表示障碍物（不可通行）

目标：

所有与矩阵边界相连的 0 保持 0。

所有被 1 完全包围的 0 改为 2。

1 保持不变。

示例输入：

text
5
1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 1
示例输出：

text
1 1 1 1 1
1 0 0 0 1
1 0 1 0 1
1 0 0 0 1
1 1 1 1 1
2. 解题思路
核心思想
从边界出发，用 BFS/DFS 标记所有可达的 0：

如果 0 能通过上下左右移动到达边界，则它属于“边界连通区域”，保持 0。

如果 0 被 1 完全包围，无法到达边界，则改为 2。

算法选择
BFS（广度优先搜索）：

使用队列逐层遍历，适合较大的矩阵（避免递归栈溢出）。

DFS（深度优先搜索）：

递归实现更简洁，但可能栈溢出（适用于小矩阵）。

步骤
输入矩阵。

遍历所有边界点：

如果 vis[i][j] == 0，则进行 BFS/DFS 标记所有可达的 0 为 2。

输出矩阵：

1 保持 1（障碍物）。

2 表示原本是 0 但被 BFS/DFS 访问过（边界连通区域）。

0 表示未被访问的 0（被 1 包围的区域）。

3. 代码实现（BFS版本）
   cpp
   #include <bits/stdc++.h>
   using namespace std;

int vis[35][35]; // 矩阵
int dx[] = {1, -1, 0, 0}; // 方向数组：下、上、右、左
int dy[] = {0, 0, 1, -1};
int n;

struct node {
int x, y; // 坐标
};

void bfs(int x1, int y1) {
queue<node> q;
q.push({x1, y1});
vis[x1][y1] = 2; // 标记为边界连通区域

while (!q.empty()) {
    node u = q.front();
    q.pop();  // 弹出队首
    
    // 检查四个方向
    for (int i = 0; i < 4; i++) {
        int nx = u.x + dx[i];
        int ny = u.y + dy[i];
        // 检查是否越界，并且是否是未访问的 0
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n && vis[nx][ny] == 0) {
            vis[nx][ny] = 2;  // 标记为已访问
            q.push({nx, ny});  // 加入队列
        }
    }
}

}

int main() {
cin >> n;
// 输入矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> vis[i][j];
}
}

// 遍历边界，进行 BFS
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if ((i == 1 || i == n || j == 1 || j == n) && vis[i][j] == 0) {
            bfs(i, j);
        }
    }
}

// 输出结果
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (vis[i][j] == 2) {
            cout << 0 << " ";  // 边界连通区域
        } else if (vis[i][j] == 1) {
            cout << 1 << " ";  // 障碍物
        } else if (vis[i][j] == 0) {
            cout << 2 << " ";  // 被包围的 0
        }
    }
    cout << endl;
}

return 0;

}
4. 代码实现（DFS版本）
cpp
#include <bits/stdc++.h>
using namespace std;

int vis[35][35];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int n;

void dfs(int x, int y) {
if (x < 1 || x > n || y < 1 || y > n || vis[x][y] != 0) return;
vis[x][y] = 2; // 标记为边界连通区域
for (int i = 0; i < 4; i++) {
dfs(x + dx[i], y + dy[i]); // 递归搜索四个方向
}
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> vis[i][j];
}
}

// 遍历边界，进行 DFS
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if ((i == 1 || i == n || j == 1 || j == n) && vis[i][j] == 0) {
            dfs(i, j);
        }
    }
}

// 输出结果
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (vis[i][j] == 2) {
            cout << 0 << " ";
        } else if (vis[i][j] == 1) {
            cout << 1 << " ";
        } else if (vis[i][j] == 0) {
            cout << 2 << " ";
        }
    }
    cout << endl;
}

return 0;

}
5. 复杂度分析
算法 时间复杂度 空间复杂度
BFS O(n²) O(n²)
DFS O(n²) O(n²)（递归栈可能溢出）
BFS 更适合大矩阵（队列实现，无栈溢出风险）。

DFS 代码更简洁（递归实现，适合小矩阵）。

6. 实际应用
   图像处理：标记连通区域（如 Photoshop 的魔棒工具）。

游戏地图生成：判断封闭区域（如迷宫的可达性分析）。

自动化测试：检测 UI 元素的封闭性。

7. 总结
   BFS/DFS 是解决连通性问题的经典方法。

从边界出发，标记所有可达的 0。

注意 = 和 == 的区别（常见错误）。

BFS 用队列，DFS 用递归/栈，选择适合的算法。