P1162 填涂颜色

admin

https://www.luogu.org/problemnew/show/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≤n≤30)

接下来 n 行，由 0和 1 组成的 n×n 的方阵。

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

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

输出格式：
已经填好数字 2 的完整方阵。

输入输出样例
输入样例#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≤n≤30

universehyf

198个广搜

1. #include<iostream>
   
2. using namespace std;
   
3. #define FOR(iii,nn,mm) for(int iii=nn;iii<=mm;iii++)
   
4. int dr[4]={-1,0,1,0};
   
5. int dc[4]={0,-1,0,1};
   
6. int q[2600][2];
   
7. int a[51][51];
   
8. bool b[51][51];
   
9. int t,r,c,n,head,tail;
   
10. int main()
    
11. {
    
12.     cin>>n;
    
13.     FOR(i,0,n-1) FOR(j,0,n-1) cin>>a[i][j];
    
14.     FOR(i,0,n-1)if((!b[0][i])&&a[0][i]==0)
    
15.     {r=0;c=i;q[1][0]=r;q[1][1]=c;b[r][c]=1;head=0;tail=1;do{
    
16.         head++;r=q[head][0];c=q[head][1];FOR(k,0,3)
    
17.         if(r+dr[k]<=n-1&&c+dc[k]<=n-1&&(!b[r+dr[k]][c+dc[k]])&&a[r+dr[k]][c+dc[k]]==0)
    
18.         {tail++;b[r+dr[k]][c+dc[k]]=1;q[tail][0]=r+dr[k];q[tail][1]=c+dc[k];}
    
19.     }while(head<tail);}
    
20.     FOR(i,0,n-1)if((!b[n-1][i])&&a[n-1][i]==0)
    
21.     {r=n-1;c=i;q[1][0]=r;q[1][1]=c;b[r][c]=1;head=0;tail=1;do{
    
22.         head++;r=q[head][0];c=q[head][1];FOR(k,0,3)
    
23.         if(r+dr[k]<=n-1&&c+dc[k]<=n-1&&(!b[r+dr[k]][c+dc[k]])&&a[r+dr[k]][c+dc[k]]==0)
    
24.         {tail++;b[r+dr[k]][c+dc[k]]=1;q[tail][0]=r+dr[k];q[tail][1]=c+dc[k];}
    
25.     }while(head<tail);}
    
26.     FOR(i,1,n-2) if((!b[i][0])&&a[i][0]==0)
    
27.     {r=i;c=0;q[1][0]=r;q[1][1]=c;b[r][c]=1;head=0;tail=1;do{
    
28.         head++;r=q[head][0];c=q[head][1];FOR(k,0,3)
    
29.         if(r+dr[k]<=n-1&&c+dc[k]<=n-1&&(!b[r+dr[k]][c+dc[k]])&&a[r+dr[k]][c+dc[k]]==0)
    
30.         {tail++;b[r+dr[k]][c+dc[k]]=1;q[tail][0]=r+dr[k];q[tail][1]=c+dc[k];}
    
31.     }while(head<tail);}
    
32.     FOR(i,1,n-2)if((!b[i][n-1])&&a[i][n-1]==0)
    
33.     {r=i;c=n-1;q[1][0]=r;q[1][1]=c;b[r][c]=1;head=0;tail=1;do{
    
34.         head++;r=q[head][0];c=q[head][1];FOR(k,0,3)
    
35.         if(r+dr[k]<=n-1&&c+dc[k]<=n-1&&(!b[r+dr[k]][c+dc[k]])&&a[r+dr[k]][c+dc[k]]==0)
    
36.         {tail++;b[r+dr[k]][c+dc[k]]=1;q[tail][0]=r+dr[k];q[tail][1]=c+dc[k];}
    
37.     }while(head<tail);}
    
38.     ///FOR(i,0,n-1) {FOR(j,0,n-1) cout<<a[i][j]<<" ";cout<<endl;}
    
39.     FOR(i,0,n-1) {FOR(j,0,n-1)
    
40.     {if(a[i][j]==0)
    
41.      {
    
42.         if(b[i][j]) cout<<0;
    
43.         else cout<<2;
    
44.      }else cout<<1;
    
45.      cout<<" ";
    
46.     }cout<<endl;}
    
47.     return 0;
    
48. }

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int a[31][31];
   
4. int n,x,y;
   
5. void dfs(int x,int y)
   
6. {
   
7.     a[x][y]=2;
   
8.     if(!a[x][y+1])dfs(x,y+1);
   
9.     if(!a[x+1][y])dfs(x+1,y);
   
10.     if(!a[x][y-1])dfs(x,y-1);
    
11.     if(!a[x-1][y])dfs(x-1,y);
    
12. }
    
13. int main()
    
14. {
    
15.     cin>>n;
    
16.     for(int i=1;i<=n;i++)
    
17.         for(int j=1;j<=n;j++)
    
18.     {
    
19.         cin>>a[i][j];
    
20.         if(!x&&!y&&a[i][j]==1)x=i,y=j;
    
21.     }
    
22.     dfs(x+1,y+1);
    
23.     for(int i=1;i<=n;i++)
    
24.         {
    
25.             for(int j=1;j<=n;j++)cout<<a[i][j]<<' ';
    
26.             cout<<endl;
    
27.         }
    
28.     return 0;
    
29. }
    

复制代码

倚窗倾听风吹雨

1. #include<iostream>
   
2. using namespace std;
   
3. int n,a[32][32],er;
   
4. bool k[32][32];
   
5. struct node
   
6. {
   
7.     int r,c;
   
8. }b[1000000];
   
9. bool visit[32][32];
   
10. int main()
    
11. {
    
12.     cin>>n;
    
13.     for(int i=1;i<=n;i++)
    
14.       for(int j=1;j<=n;j++)
    
15.         cin>>a[i][j];
    
16.     for(int i=1;i<=n;i++)
    
17.       for(int j=1;j<=n;j++)
    
18.     {
    
19.         if(a[i][j])continue;
    
20.         int head=0,tail=1;
    
21.         b[head].r=i;
    
22.         b[head].c=j;
    
23.         visit[i][j]=1;
    
24.         k[i][j]=1;
    
25.         while(head<tail)
    
26.         {
    
27.             if(b[head].r==0 || b[head].c==0 || b[head].r==n+1 || b[head].c==n+1)
    
28.             {
    
29.                 for(int i=0;i<=n+1;i++)
    
30.                     for(int j=0;j<=n+1;j++)
    
31.                     {
    
32.                         k[i][j]=0;
    
33.                         visit[i][j]=0;
    
34.                     }
    
35.                 break;
    
36.             }
    
37.             if(!a[b[head].r+1][b[head].c] && !visit[b[head].r+1][b[head].c])
    
38.             {
    
39.                 b[tail].r=b[head].r+1;
    
40.                 b[tail].c=b[head].c;
    
41.                 k[b[head].r+1][b[head].c]=1;
    
42.                 visit[b[head].r+1][b[head].c]=1;
    
43.                 tail++;
    
44.             }
    
45.             if(!a[b[head].r][b[head].c+1] && !visit[b[head].r][b[head].c+1])
    
46.             {
    
47.                 b[tail].r=b[head].r;
    
48.                 b[tail].c=b[head].c+1;
    
49.                 k[b[head].r][b[head].c+1]=1;
    
50.                 visit[b[head].r][b[head].c+1]=1;
    
51.                 tail++;
    
52.             }
    
53.             if(!a[b[head].r][b[head].c-1] && !visit[b[head].r][b[head].c-1])
    
54.             {
    
55.                 b[tail].r=b[head].r;
    
56.                 b[tail].c=b[head].c-1;
    
57.                 k[b[head].r][b[head].c-1]=1;
    
58.                 visit[b[head].r][b[head].c-1]=1;
    
59.                 tail++;
    
60.             }
    
61.             if(!a[b[head].r-1][b[head].c] && !visit[b[head].r-1][b[head].c])
    
62.             {
    
63.                 b[tail].r=b[head].r-1;
    
64.                 b[tail].c=b[head].c;
    
65.                 visit[b[head].r-1][b[head].c]=1;
    
66.                 k[b[head].r-1][b[head].c]=1;
    
67.                 tail++;
    
68.             }
    
69.             head++;
    
70.         }
    
71.         if(head==tail)
    
72.         {
    
73.             for(int l=1;l<=n;l++)
    
74.             {
    
75.                 for(int m=1;m<=n;m++)
    
76.                 if(k[l][m])cout<<"2 ";
    
77.                 else cout<<a[l][m]<<" ";
    
78.                 cout<<endl;
    
79.             }
    
80.             return 0;
    
81.         }
    
82.     }
    
83.    return 0;
    
84. }
    

复制代码