华师一附中OI组

标题: P1162 填涂颜色 [打印本页]
作者: admin    时间: 2018-6-29 17:20
标题: P1162 填涂颜色
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
作者: 倚窗倾听风吹雨    时间: 2018-8-20 10:09
  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. }
复制代码
作者: 黄煦喆    时间: 2018-8-28 22:45
  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. }
复制代码
作者: universehyf    时间: 2018-9-25 19:31
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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2