洛谷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(n2)
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <queue> 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<xOy> 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<<b[i][j]<<" "; 57 cout<<endl; 58 } 59 return 0; 60 }
原文：http://www.cnblogs.com/maopengsen/p/4469894.html