p1162 填涂颜色

xiaoxiao2021-02-28  14

题目链接: 点击打开链接 很经典的一道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; } } //完美的结束

转载请注明原文地址: https://www.6miu.com/read-2250073.html

最新回复(0)