p1162 填涂颜色

题目链接： 点击打开链接 很经典的一道bfs（广度优先搜索）（我看大佬们说的） 所以蒟蒻的我奉上两种思路 描述：

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

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

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

输出格式：

已经填好数字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：

从四个角开始bfs搜索，把所有圈外面的零变成2， 最后判断输出结果。 code： #include<bits/stdc++.h> using namespace std; int m[31][31]; int fx[4]={1,-1,0,0},//上，下，左，右四个方向 fy[4]={0,0,-1,1}; int n; void print();//输出 void bfs(int,int);//判断 int main() { cin>>n; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cin>>m[i][j]; for(int i=1;i<=n;++i)//从四个角开始判断 { if(!m[i][1]) bfs(i,1); if(!m[1][i]) bfs(1,i); if(!m[n][i]) bfs(n,i); if(!m[i][n]) bfs(i,n); } print();//输出 return 0; } void bfs(int p,int q) { int x,y; int head=0,tail=1;//头指针与尾指针 m[p][q]=2;//将圈外面的0变成二 int dx[1011],dy[1011];//一定要大一点，否则会超内存 dx[1]=p;//记录 dy[1]=q; do { head++;//头指针加一，入库 for(int i=0;i<=3;++i)//四个方向判断 { x=dx[head]+fx[i];//方向 y=dy[head]+fy[i]; if(x>=1&&x<=n&&y>=1&&y<=n&&!m[x][y])//是否在数据里面和是否为零 { tail++;//尾指针加一 dx[tail]=x;//记录位置 dy[tail]=y; m[x][y]=2;//变成零 } } }while(head<tail); } void print() { for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { if(!m[i][j])//如果为零，表示在圈内，输出2 cout<<2<<" "; else if(m[i][j]==2)//如果等于2，说明这个位置原先在圈外 cout<<0<<" "; else cout<<1<<" ";//输出原来的1 } cout<<endl; } }

思路2： 根据题意，第一个1的位置的右下角一定在圈内，找到第一个1的位置，然后从它的右下角开始bfs搜索，把所有圈内的零变成2，最后直接输出数据即可。

code： #include<bits/stdc++.h> using namespace std; int m[31][31]; int fx[4]={1,-1,0,0},//上，下，左，右四个方向 fy[4]={0,0,-1,1}; int n; void print();//输出 void bfs(int,int);//判断 int main() { cin>>n; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) cin>>m[i][j]; for(int i=1;i<=n;++i)//从四个角开始判断 { for(int j=1;j<=n;++j) { if(m[i][j])//寻找位置 { bfs(i+1,j+1); print(); return 0; } } } return 0; } void bfs(int p,int q) { int x,y; int head=0,tail=1;//头指针与尾指针 m[p][q]=2;//将圈外面的0变成二 int dx[1011],dy[1011];//一定要大一点，否则会超内存 dx[1]=p;//记录 dy[1]=q; do { head++;//头指针加一，入库 for(int i=0;i<=3;++i)//四个方向判断 { x=dx[head]+fx[i];//方向 y=dy[head]+fy[i]; if(x>=1&&x<=n&&y>=1&&y<=n&&!m[x][y])//是否在数据里面和是否为零 { tail++;//尾指针加一 dx[tail]=x;//记录位置 dy[tail]=y; m[x][y]=2;//变成零 } } }while(head<tail); } void print() { for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) { cout<<m[i][j]<<" "; } cout<<endl; } } //完美的结束