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; // 标记为边界连通区域
}
int main() {
cin >> n;
// 输入矩阵
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> vis[i][j];
}
}
}
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];
}
}
}
5. 复杂度分析
算法 时间复杂度 空间复杂度
BFS O(n²) O(n²)
DFS O(n²) O(n²)（递归栈可能溢出）
BFS 更适合大矩阵（队列实现，无栈溢出风险）。
DFS 代码更简洁（递归实现，适合小矩阵）。
6. 实际应用
图像处理：标记连通区域（如 Photoshop 的魔棒工具）。
游戏地图生成：判断封闭区域（如迷宫的可达性分析）。
自动化测试：检测 UI 元素的封闭性。
7. 总结
BFS/DFS 是解决连通性问题的经典方法。
从边界出发，标记所有可达的 0。
注意 = 和 == 的区别（常见错误）。
BFS 用队列，DFS 用递归/栈，选择适合的算法。
