「CF525D」Arthur and Walls

冷不防 2023-08-17 17:24 139阅读 0赞

### 题目链接 ###

[戳我][Link 1]

### \\(Solution\\) ###

如果一个`#`要更改，那么一个四个格子的正方形只有他一个是`#`,bfs弄一下就好了

### \\(Code\\) ###

#include<bits/stdc++.h> using namespace std; const int inf=1e9,mod=1e9+7; typedef long long ll; int read() { int x=0,f=1; char c=getchar(); while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar(); while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } struct node { int x,y; }; queue<node> q; int n,m; char a[3001][3001]; int c[3001][3001]; int b[10]; int fx[10]= {0,0,0,1,-1}; int fy[10]= {0,1,-1,0,0}; void bfs() { while(!q.empty()) { node now=q.front(); q.pop(); int x=now.x,y=now.y; b[1]=b[2]=b[3]=b[4]=0; if(x!=1&&y!=1) b[1]=c[x-1][y-1]+c[x-1][y]+c[x][y-1]; if(x!=1&&y!=m) b[2]=c[x-1][y+1]+c[x-1][y]+c[x][y+1]; if(x!=n&&y!=1) b[3]=c[x+1][y-1]+c[x+1][y]+c[x][y-1]; if(x!=n&&y!=m) b[4]=c[x+1][y+1]+c[x+1][y]+c[x][y+1]; if(b[1]==1) { if(c[x-1][y-1]) q.push((node){x-1,y-1}),c[x-1][y-1]=0; if(c[x-1][y]) q.push((node){x-1,y}),c[x-1][y]=0; if(c[x][y-1]) q.push((node){x,y-1}),c[x][y-1]=0; } if(b[2]==1) { if(c[x-1][y+1]) q.push((node){x-1,y+1}),c[x-1][y+1]=0; if(c[x-1][y]) q.push((node){x-1,y}),c[x-1][y]=0; if(c[x][y+1]) q.push((node){x,y+1}),c[x][y+1]=0; } if(b[3]==1) { if(c[x+1][y-1]) q.push((node){x+1,y-1}),c[x+1][y-1]=0; if(c[x+1][y]) q.push((node){x+1,y}),c[x+1][y]=0; if(c[x][y-1]) q.push((node){x,y-1}),c[x][y-1]=0; } if(b[4]==1) { if(c[x+1][y+1]) q.push((node){x+1,y+1}),c[x+1][y+1]=0; if(c[x+1][y]) q.push((node){x+1,y}),c[x+1][y]=0; if(c[x][y+1]) q.push((node){x,y+1}),c[x][y+1]=0; } } } main() { n=read(),m=read(); for(int i=1; i<=n; i++) { scanf("%s",a[i]+1); for(int j=1; j<=m; j++){ if(a[i][j]=='.') q.push((node) {i,j}); else c[i][j]=1; } } bfs(); for(int i=1;i<=n;i++,cout<<endl) for(int j=1;j<=m;j++) if(c[i][j]==1) cout<<"*"; else cout<<"."; }

转载于:https://www.cnblogs.com/hbxblog/p/11412615.html

[Link 1]: https://www.luogu.org/problem/CF525D