「CF525D」Arthur and Walls

\(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<<"."; 
}

「CF525D」Arthur and Walls

原文：https://www.cnblogs.com/hbxblog/p/11412615.html