「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

\(Solution\)

\(Code\)

最新文章

热门文章