【题目来源】
洛谷：P1162 填涂颜色 - 洛谷
【题目描述】
由数字 \(0\) 组成的方阵中，有一任意形状闭合圈，闭合圈由数字 \(1\) 构成，围圈时只走上下左右 \(4\) 个方向。现要求把闭合圈内的所有空间都填写成 \(2\)。例如：\(6\times 6\) 的方阵（\(n=6\)），涂色前和涂色后的方阵如下：
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
【输入】
每组测试数据第一行一个整数 \(n(1\le n\le 30)\)。
接下来 \(n\) 行，由 \(0\) 和 \(1\) 组成的 \(n\times n\) 的方阵。
方阵内只有一个闭合圈，圈内至少有一个 \(0\)。
【输出】
已经填好数字 \(2\) 的完整方阵。
【输入样例】
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
【输出样例】
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
【解题思路】
【算法标签】
《洛谷 P1162 填图颜色》 #搜索# #广度优先搜索,BFS# #队列# #洛谷原创#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int n, tmp; // n: 矩阵大小, tmp: 临时变量
// 四个方向的偏移量：上、右、下、左
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int a[35][35] = {0}; // 存储原始矩阵
int vis[35][35] = {0}; // 标记数组，记录是否访问过// 定义坐标结构体
struct node
{int x, y;
};int main()
{// 输入矩阵大小cin >> n;// 输入矩阵数据for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> tmp;if (tmp == 1) {a[i][j] = 1; // 标记为1的位置}}}// 初始化BFS队列，从(0,0)开始queue<node> q;node tp = {0, 0};q.push(tp);vis[0][0] = 1; // 标记起点为已访问// BFS遍历所有可达的0区域while (!q.empty()) {node tp = q.front();q.pop();// 遍历四个方向for (int i = 0; i < 4; i++) {int xx = tp.x + dx[i];int yy = tp.y + dy[i];// 检查边界if (xx < 0 || xx > n + 1 || yy < 0 || yy > n + 1) {continue;}// 如果是0且未访问过if (a[xx][yy] == 0 && vis[xx][yy] == 0) {vis[xx][yy] = 1; // 标记为已访问node t = {xx, yy};q.push(t); // 加入队列}}}// 输出处理后的矩阵for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (a[i][j] == 0 && vis[i][j] == 0) {cout << 2 << " "; // 被1包围的0区域标记为2}else if (a[i][j] == 1) {cout << 1 << " "; // 原始1保持不变}else {cout << 0 << " "; // 可达的0区域}}cout << endl;}return 0;
}
【运行结果】
6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1