首页 > 代码库 > 颜色填涂——过于水的bfs

颜色填涂——过于水的bfs

  扫一遍填色,如果当前扫的点在整个矩形的边界上,记录此为外界。不是外界的点,输出时输出2

技术分享
 1 #include<queue> 2 #include<cstdio> 3 #include<iostream> 4 using namespace std; 5 const int N=32,ax[]={1,-1,0,0},ay[]={0,0,1,-1}; 6 struct node{int x,y;}; 7 int n,cnt=1,col[N][N]; 8 bool gr[N][N],vis[N][N],out[N]; 9 void bfs(int sx,int sy){10     queue<node> q;11     q.push((node){sx,sy});12     vis[sx][sy]=true;13     col[sx][sy]=cnt;14     while(!q.empty()){15         node now=q.front();q.pop();16         for(int i=0;i<4;i++){17             int nx=ax[i]+now.x,ny=ay[i]+now.y;18             if(vis[nx][ny]||nx>n||ny>n||nx<1||ny<1||gr[nx][ny]!=gr[sx][sy])19                 continue;20             if(nx==1||ny==1||nx==n||ny==n)out[cnt]=true;21             col[nx][ny]=cnt;22             vis[nx][ny]=true;23             q.push((node){nx,ny});24         }25     }26 }27 int main(){28     freopen("zenith.txt","r",stdin);29     cin>>n;30     for(int i=1;i<=n;i++)31         for(int j=1;j<=n;j++)32             cin>>gr[i][j];33     for(int i=1;i<=n;i++)34         for(int j=1;j<=n;j++)35             if(!vis[i][j]&&!gr[i][j]){36                 bfs(i,j);37                 cnt++;38             }39     for(int i=1;i<=n;i++){40         for(int j=1;j<=n;j++)41             if(out[col[i][j]]||gr[i][j])cout<<gr[i][j]<<" ";42             else cout<<2<<" ";43         cout<<endl;44     }45     return 0;46 }
Method_01

  洛谷 0ms

颜色填涂——过于水的bfs