记录学习
填涂颜色
题目描述
由数字 $0$ 组成的方阵中，有一任意形状的由数字 $1$ 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 $2$。例如：$6\times 6$ 的方阵（$n=6$），涂色前和涂色后的方阵如下：
如果从某个 $0$ 出发，只向上下左右 $4$ 个方向移动且仅经过其他 $0$ 的情况下，无法到达方阵的边界，就认为这个 $0$ 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 $0$ 是连通的（两两之间可以相互到达）。
1
2
3
4
5
6
|
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
|
1
2
3
4
5
6
|
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 \le n \le 30)$。
接下来 $n$ 行，由 $0$ 和 $1$ 组成的 $n \times n$ 的方阵。
方阵内只有一个闭合圈，圈内至少有一个 $0$。
输出格式
已经填好数字 $2$ 的完整方阵。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
|
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
1
2
3
4
5
6
|
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%$ 的数据，$1 \le n \le 30$。
思路
1.输入矩阵
2.进行BFS搜索，标记搜索过的
3.输出，如果值为零且未被标记，则一定是被包围的，就输出2
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
|
#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;
}
|