首页 > 代码库 > 颜色填涂——过于水的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 }
洛谷 0ms
颜色填涂——过于水的bfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。