P1162 填涂颜色
对应章节：五、数据结构与算法 → （十二） 搜索：递归、回溯、DFS、BFS 与记忆化。
（一） 任务与输出目标
把闭合圈内的 0 改成 2，圈外的 0 保留。
（二） 建模与推导
直接猜圈内起点很难，先找所有圈外格子。给方阵外面补一圈 0，从外圈角落 BFS，只经过 0。能到达的是外部；搜索结束后，未到达的 0 都被 1 围住，输出 2。补圈让四条边的外部自然连成一个起点可达区域。
（三） 手算与过程
3×3 中外围全为 1、中心为 0：外部 BFS 无法进入中心，中心输出 2。
（四） 带注释实现
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
int n;
cin >> n;
vector<vector<int>> a(n + 2, vector<int>(n + 2, 0));
vector<vector<bool>> outside(n + 2, vector<bool>(n + 2, false));
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
cin >> a[i][j];
queue<pair<int, int>> q;
q.emplace(0, 0);
outside[0][0] = true;
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
for (int d = 0; d < 4; ++d) {
int u = x + dx[d], v = y + dy[d];
if (u >= 0 && u <= n + 1 && v >= 0 && v <= n + 1 && !a[u][v] && !outside[u][v]) {
outside[u][v] = true;
q.emplace(u, v); // 从外面到达的 0 保持原样。
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (a[i][j] == 0 && !outside[i][j])
a[i][j] = 2;
cout << a[i][j] << ' ';
}
cout << '\n';
}
}
signed main() {
ios::sync_with_stdio(false); // 关闭同步，使用 cin 与 cout 完成输入输出。
cin.tie(0), cout.tie(0);
int T = 1; // 本题读入一组数据。
// cin >> T; // 题目给出测试组数时开启，并在 solve 中处理一组。
while (T--)
solve();
}（五） 复杂度
时间与空间均为 \(O(n^2)\)。