洛谷P1162 填涂颜色 解题报告

by MedalPluS

题目描述:

     由数字0 组成的方阵中，有一任意形状闭合圈，闭合圈由数字1构成，围圈时只走上下左右4个方向。现要求把闭合圈内的所有空间都填写成2.例如：6X6的方阵（n=6），涂色前和   涂色后的方阵如下：
0 0 0 0 0 0      0 0 0 0 0 0
0 0 1 1 1 1      0 0 1 1 1 1
0 1 1 0 0 1      0 1 1 2 2 1
1 1 0 0 0 1      1 1 2 2 2 1 
1 0 0 0 0 1      1 2 2 2 2 1
1 1 1 1 1 1      1 1 1 1 1 1

输入格式：

每组测试数据第一行一个整数：n。其中n(1<=n<=30)
接下来n行，由0和1组成的nXn的方阵。
方阵内只有一个闭合圈，圈内至少有一个0。

输出格式：

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

分析：

首先根据题目的意思，就是将被1包围的0改为2

直接做不好做，我们来研究一下，题目是求被1包围，注意，包围

没错！那么反过来思考，就很好做了，只要将没有被包围的填充为0，其余都是2

我们先开辟一个数组b，记录输入a，但是，首先b全赋值为2，然后对于a，如果有(i,j)为1，则b(i,j)=1

然后BFS，起始状态就是与边界相通的格子，然后就能BFS，对于每一个能拓展到的0的格子，就将其在b数组中变为0

然后拓展结束后b数组就是答案

时间复杂度O(n²)

代码：

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 using namespace std; 5  6 const int maxn=101; 7  8 int a[maxn][maxn],b[maxn][maxn]; 9 int n;10 bool vis[maxn][maxn];11 12 struct xOy{13     int x,y;14 };15 16 void bfs(){17     queue
        
          q;18     xOy head;19     int i;20     for(i=1;i<=n;i++){21       if(a[i][1]==0)q.push((struct xOy){i,1});22       if(a[i][n]==0)q.push((struct xOy){i,n});23     }24     for(i=1;i<=n;i++){25       if(a[1][i]==0)q.push((struct xOy){
   1,i});26       if(a[n][i]==0)q.push((struct xOy){n,i});27     }28     while(!q.empty()){29         head=q.front();30         q.pop();31         if(vis[head.x][head.y])continue;32         vis[head.x][head.y]=true;33         b[head.x][head.y]=0;34         if(head.x-1>0 && a[head.x-1][head.y]==0)q.push((struct xOy){head.x-1,head.y});35         if(head.x+1<=n && a[head.x+1][head.y]==0)q.push((struct xOy){head.x+1,head.y});36         if(head.y-1>0 && a[head.x][head.y-1]==0)q.push((struct xOy){head.x,head.y-1});37         if(head.y+1<=n && a[head.x][head.y+1]==0)q.push((struct xOy){head.x,head.y+1});38     }39     return ;40 }41 42 int main(){43     cin>>n;44     int i,j;45     for(i=1;i<=n;i++)46       for(j=1;j<=n;j++)47         b[i][j]=2;48     for(i=1;i<=n;i++)49       for(j=1;j<=n;j++){50         cin>>a[i][j];51         if(a[i][j]==1)b[i][j]=1;52     }53     bfs();54     for(i=1;i<=n;i++){55       for(j=1;j<=n;j++)56         cout<
         
          <<" ";57       cout<