记录学习
填涂颜色
题目描述
由数字 0 0 0 组成的方阵中，有一任意形状的由数字 1 1 1 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 2 2 2。例如： 6 × 6 6\times 6 6×6 的方阵（ n = 6 n=6 n=6），涂色前和涂色后的方阵如下：
如果从某个 0 0 0 出发，只向上下左右 4 4 4 个方向移动且仅经过其他 0 0 0 的情况下，无法到达方阵的边界，就认为这个 0 0 0 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 0 0 0 是连通的（两两之间可以相互到达）。
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1
输入格式
每组测试数据第一行一个整数 n ( 1 ≤ n ≤ 30 ) n(1 \le n \le 30) n(1≤n≤30)。
接下来 n n n 行，由 0 0 0 和 1 1 1 组成的 n × n n \times n n×n 的方阵。
方阵内只有一个闭合圈，圈内至少有一个 0 0 0。
输出格式
已经填好数字 2 2 2 的完整方阵。
样例 #1
样例输入 #1
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
样例输出 #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
提示
对于 100 % 100\% 100% 的数据， 1 ≤ n ≤ 30 1 \le n \le 30 1≤n≤30。
思路
1.输入矩阵
2.进行BFS搜索，标记搜索过的
3.输出，如果值为零且未被标记，则一定是被包围的，就输出2
代码
#include <iostream>
#include <queue>
using namespace std;
struct point {
int x = 0;
int y = 0;
};
queue<point> q;
int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 };
int land[35][35] = {0}, mark[35][35] = {0}, n, tmp;
int main() {
cin >> n;
//输入
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> tmp;
if (tmp == 1) {
land[i][j] = tmp;
}
}
}
//把起始点标记为经过
mark[0][0] = 1;
q.push(point{0,0});
//开始bfs搜索
while (!q.empty()) //一直到搜索完成
{
point p = q.front(); //取出搜索队列的第一个元素
q.pop(); //弹出第一个元素
//前后左右
for (int i = 0; i < 4; i++) {
int x = dx[i] + p.x;
int y = dy[i] + p.y;
//如果越界，就跳出此次循环
if (x < 0 && x > n && y < 0 && y > n ) continue;
//如果未被搜索且数值为零
if (land[x][y] == 0 && mark[x][y] == 0) {
mark[x][y] = 1; //标记为已经搜索
q.push(point{ x,y }); //加入搜索队列
}
}
}
cout << endl;
//遍历矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
//如果没被搜索过
if (land[i][j] == 0 && mark[i][j] == 0) {
cout << 2 << " "; //说明被包围，则输出2
}
else if (land[i][j] == 1) {
cout << 1 << " "; //1就是边界
}
else {
cout << 0 << " "; //否则就是搜过的0
}
}
cout << endl;
}
return 0;
}