P1162 填涂颜色
题目描述
由数字 \(0\) 组成的方阵中，有一任意形状的由数字 \(1\) 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 \(2\)。例如：\(6\times 6\) 的方阵（\(n=6\)），涂色前和涂色后的方阵如下：
如果从某个 \(0\) 出发，只向上下左右 \(4\) 个方向移动且仅经过其他 \(0\) 的情况下，无法到达方阵的边界，就认为这个 \(0\) 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 \(0\) 是连通的（两两之间可以相互到达）。
输入格式
每组测试数据第一行一个整数 \(n(1 \le n \le 30)\)。
接下来 \(n\) 行，由 \(0\) 和 \(1\) 组成的 \(n \times n\) 的方阵。
方阵内只有一个闭合圈，圈内至少有一个 \(0\)。
输出格式
已经填好数字 \(2\) 的完整方阵。
输入输出样例 #1
输入 #1
输出 #1
说明/提示
对于 \(100\%\) 的数据，\(1 \le n \le 30\)。
Tip
📌 题目分析
给定数据：
由数字 0 和 1 组成，1 构成了一个闭合圈。要求把圈内的 0 全部变成 2 并输出最终的矩阵。
👉 本质：
👉 类型：
🧠 解题思路
1️⃣ 为什么要用逆向思维？
如果我们直接去找“被 1 包围的 0”，判定条件会非常复杂，因为闭合圈的形状是不规则的，你很难判断一个 0 到底是不是真的在圈内。
但是，找“圈外的 0”极其简单！
圈外的 0 有一个绝对的特征：它们一定能和矩阵的边界相连通。
所以，只要我们把圈外所有的 0 全部找出来并打上标记，剩下的那些没被打标记的 0，必定就是被困在圈内的！
2️⃣ 核心技巧：矩阵外扩 (Padding)
如果我们直接在原矩阵的边界上找 0 进行搜索，需要写四个 for 循环分别遍历上下左右四条边，非常繁琐，而且容易漏掉某些角落。
神仙操作：我们在原有的 n × n 矩阵外面，人为地加上一圈 0。
原来矩阵的下标是 1 到 n。我们把数组稍微开大一点，包含第 0 行、第 0 列、第 n+1 行、第 n+1 列，并且默认全为 0。
这样，矩阵外部所有的 0 都连成了一片“汪洋大海”。我们只需要从坐标 (0, 0) 开始进行一次 Flood Fill（泛洪搜索），就能把所有圈外的 0 全部找出来！
3️⃣ 状态映射
定义数组的值：
* 1：墙壁（闭合圈本身）。
* 0：未被访问过的原始空格。
* 3（或者其他数字）：我们在搜索时，把圈外的 0 全部染成 3。
搜索结束后，遍历原矩阵的 1 到 n 范围：
* 如果遇到 3，说明是外面的，输出 0。
* 如果遇到 1，说明是墙壁，输出 1。
* 如果遇到 0，说明搜索没波及到它，它是圈内的，输出 2！
💻 C++代码
#include <iostream>
#include <queue>
using namespace std;
int n;
// 数组开到 35，利用全局数组自动初始化为 0 的特性，天然形成了“外扩圈”
int grid[35][35];
// 方向数组：上下左右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
// 广度优先搜索 (Flood Fill)
void bfs(int startX, int startY) {
queue<pair<int, int>> q;
q.push({startX, startY});
grid[startX][startY] = 3; // 把圈外的 0 标记为 3
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 注意边界：包含扩充的 0 到 n+1
// 只有遇到原始的 0 才会继续蔓延
if (nx >= 0 && nx <= n + 1 && ny >= 0 && ny <= n + 1 && grid[nx][ny] == 0) {
grid[nx][ny] = 3; // 染色
q.push({nx, ny});
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
// 输入数据，注意下标从 1 开始，正好空出了 0 行 0 列
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> grid[i][j];
}
}
// 从我们人为制造的“超级起点” (0,0) 开始泛洪
bfs(0, 0);
// 按要求输出结果
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (grid[i][j] == 0) {
cout << 2 << " "; // 没被染色的 0 就是圈内的
} else if (grid[i][j] == 3) {
cout << 0 << " "; // 被染色的 3 还原成圈外的 0
} else {
cout << 1 << " "; // 墙壁 1 保持不变
}
}
cout << "\n";
}
return 0;
}
⚠️ 易错点
❌ 1. 数组越界与边界条件
在使用 Padding 技巧时，矩阵的实际有效范围扩大到了 0 到 n+1。
所以在 bfs 函数中判定是否越界时，必须写成 nx <= n + 1 和 ny <= n + 1。如果还是习惯性地写 nx < n，会导致外扩的那一圈被截断，洪水无法绕过闭合圈流到另一边。
❌ 2. 搜索到了圈内
如果不用 Padding 技巧，而是从内部随便找一个 0 开始搜，你根本不知道这个 0 是在圈内还是圈外。核心法则是：必须从绝对在外部的坐标起手。
❌ 3. 连通性判定错误
这道题目明确了“从某个 0 出发，只向上下左右 4 个方向移动”。对角线上的 1 是可以完美封死路线的。方向数组切记只能写 4 个方向，写成 8 方向洪水就会顺着对角线缝隙“漏”进圈内，把里面的 0 全染了。
🚀 一句话总结
🔥 补充
硬核知识点：虚拟源点 (Dummy Node) 与边界扩充 (Padding)
这道题使用的技巧在图论和计算机图形学中非常经典。
* 边界扩充 (Padding)：在卷积神经网络 (CNN) 处理图像时，为了不忽略边缘像素的特征，常常会在图像最外圈补一圈 0（即 Zero-padding）。这与我们在算法题中补一圈 0 防止搜索死角的思想如出一辙。
* 虚拟源点 (Dummy Node)：当一个图有多个起点需要同时进行 BFS（比如求多个基地的最短距离），最暴力的做法是跑多次 BFS。而最高效的做法是：凭空创造一个“虚拟坐标”，让它到所有实际起点的距离都为 0。这就相当于把多个起点的多源 BFS，强行降维成了一个单源 BFS。本题中坐标 (0,0) 其实就充当了所有外部区域的“虚拟超级源点”。
我的做法dfs
#include<iostream>
#include<vector>
using namespace std;
int n, m;
int mp[20][20];
int dx[4] = { 1,-1,0,0};
int dy[4] = { 0,0,1,-1 };
bool vis[20][20];
void floodfill(int x,int y) {
// 基础边界检查
if (x < 0 || y < 0 || x > n + 1 || y > n + 1) return;
// 关键修正：如果是墙(1)或者已经访问过，就停止搜索
if (mp[x][y] == 1 || vis[x][y]) return;
vis[x][y] = 1;
mp[x][y] = 3;
for (int i = 0;i < 4;i++) {
int nx = x + dx[i], ny = y + dy[i];
floodfill(nx, ny);
}
return;
}
int main() {
cin >> n ;
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
cin >> mp[i][j];
}
}
floodfill(0, 0);
for (int i = 1;i <= n;i++) {
for (int j = 1;j <= n;j++) {
cout << ((mp[i][j] == 1) ? 1 : ((mp[i][j] == 3) ? 0 : 2)) << " ";
}
cout << endl;
}
return 0;
}