题解 [CF525D] Arthur and Walls

题面

解析

首先考虑将一个\('*'\)变成\('.'\)后会形成什么,

显然至少是一个\(2\times 2\)的矩形.

因为\(1\times 1\)和\(1\times 2\)的改了没用啊,

而我们考虑什么时候应该把\('*'\)改掉,

对于一个矩形,它可以看成若干个可能重叠的\(2\times 2\)的矩形,

而在一个\(2\times 2\)的矩形中,

如果有三个是\('.'\),一个是\('*'\)的话,这个\('*'\)就要改掉,

要不然是不可能拼成矩形的.

(感性理解下吧...)

所以直接对于每个\('*'\),

判断它需不需要改掉,

在\(dfs\)更新旁边的格子就行了.

(不知道为什么旁边的lzf大仙用\(bfs\)一直T)

code:(代码实现的时候有些巧妙的地方)

#include <iostream>

#include <cstdio>

#include <cstring>

#define fre(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)

using namespace std;

inline int read(){

	int sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return f*sum;

}

const int N=2005;

int n,m,a[N][N];

int pl,pr,tl,tr;

int que[N*N][3],vis[N][N];

int sta[N*N][3],top;

int dx[5]={-1,0,1,0,-1},dy[5]={0,1,0,-1,0};

char ss[N];

inline void dfs(int x,int y){

	if(a[x][y]) return ;

	if(x>n||y>m||!x||!y) return ;

	for(int k=0;k<4;k++){

		int x1=x+dx[k],y1=y+dy[k];

		int x2=x+dx[k+1],y2=y+dy[k+1];

		int x3=x+(dx[k]?dx[k]:dx[k+1]),y3=y+(dy[k]?dy[k]:dy[k+1]);

		if(a[x1][y1]&&a[x2][y2]&&a[x3][y3]){

			a[x][y]=1;

			for(int i=x-1;i<=x+1;i++)

				for(int j=y-1;j<=y+1;j++) dfs(i,j);

			return ;

		}

	}

}

int main(){

	n=read();m=read();

	for(int i=1;i<=n;i++){

		cin>>ss;

		for(int j=1;j<=m;j++) a[i][j]=(ss[j-1]=='.');

	}

	for(int i=1;i<=n;i++){

		for(int j=1;j<=m;j++) dfs(i,j);

	}

	for(int i=1;i<=n;i++,puts(""))

		for(int j=1;j<=m;j++) printf("%c",a[i][j]? '.':'*');

	return 0;

}

巴特西

题解 [CF525D] Arthur and Walls

解析

最新文章

热门文章