P1162 填涂颜色

题目描述

由数字 0 组成的方阵中，有一任意形状闭合圈，闭合圈由数字 1 构成，围圈时只走上下左右 4 个方向。现要求把闭合圈内的所有空间都填写成 2 .例如： 6×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(1≤n≤30)

接下来 nn 行，由 00 和 11 组成的 n \times nn×n 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 00 。

//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)

输出格式：

已经填好数字 22 的完整方阵。

输入输出样例

输入样例#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

说明

1≤n1≤n≤30≤30

题解

由边缘开始搜索，凡是可以到达的的00全部改为−1−1,最后输出时特判一下。

1#include <bits/stdc++.h>
2using namespace std;
3const int MAXN=50;
4int mapp[MAXN][MAXN];
5struct node{
6    int x,y;
7};
8int n;
9int dx[]={1,-1,0,0};
10int dy[]={0,0,1,-1};
11void bfs(int x,int y)
12{
13    node p;
14    p.x=x;
15    p.y=y;
16    queue<node> q;
17    q.push(p);
18    while(!q.empty()) {
19        node s;
20        s=q.front();
21        q.pop();
22        for(int i=0;i<4;i++) {
23            int kx=s.x+dx[i];
24            int ky=s.y+dy[i];
25            if(kx>=0&&kx<n&&ky>=0&&ky<n&&mapp[kx][ky]==0)
26            {
27                node z;
28                z.x=kx;z.y=ky;
29                q.push(z);
30                mapp[kx][ky]=-1;
31            }
32        }
33    }
34}
35int main()
36{
37    scanf("%d",&n);
38    for(int i=0;i<n;i++)
39        for(int j=0;j<n;j++)
40            scanf("%d",&mapp[i][j]);
41    for(int i=0;i<n;i++){
42        if(mapp[0][i]==0) bfs(0,i);
43        if(mapp[n-1][i]==0) bfs(n-1,i);
44        if(mapp[i][0]==0) bfs(i,0);
45        if(mapp[i][n-1]==0) bfs(i,n-1);
46    }
47    for(int i=0;i<n;i++){
48        for(int j=0;j<n;j++) {
49            if(mapp[i][j]==-1) printf("0 ");
50            else if(mapp[i][j]==1) printf("1 ");
51            else if(mapp[i][j]==0) printf("2 ");
52        }
53        printf("\n");
54    }
55
56    return 0;
57}