本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-26 22:08:32

Link

我一开始想的是每次选一个 . 连通块来bfs，向外扩展，由于第二次扩展开始就是矩形的扩展，可以很好地避免多次枚举同一个位置导致复杂度假掉。但这个复杂度也是假的，因为第一次扩展就是假的。第一次扩展形状是不规则的，所以很难找到一种方法使它正确的扩展。

考虑观察不规则的连通块与规则的连通块有什么不同与相同。发现不规则的连通块一定具有“向内突出的角”。形式化的说，一定存在一个 $2\times2$ 的子矩形，其中有三个 . ，一个 * 。而规则的一定没有。那么我们直接根据这个bfs即可。把所有初始的向内突出的角去掉，再找其会影响的子矩形，这个的数量显然是 $3$ 。然后继续扩展即可。

code

const int N=2e3+5;
const int dx[4]={0,0,1,1},dy[4]={0,1,0,1},Dx[8]={0,1,1,1,0,-1,-1,-1},Dy[8]={1,1,0,-1,-1,-1,0,1};

char s[N];

bool tag[N][N],vis[N][N];

bool check(int x,int y){
	if(tag[x][y])
		return 0;
	for(int i=0;i<4;i++){
		int sx=x+dx[i]-1,sy=y+dy[i]-1;
		int cnt=0;
		for(int j=0;j<4;j++)
			cnt+=tag[sx+dx[j]][sy+dy[j]];
		if(cnt==3)
			return 1;
	}return 0;
}

queue<pir> q;

signed main(){
	int n=read(),m=read();
	for(int i=1;i<=n;i++){
		scanf("%s",s+1);
		for(int j=1;j<=m;j++)
			tag[i][j]=s[j]=='.';
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(check(i,j))
				q.push({i,j}),vis[i][j]=1;
	while(!q.empty()){
		int x=q.front().fi,y=q.front().se;
		q.pop();
		tag[x][y]=1;
		for(int i=0;i<8;i++){
			int xx=x+Dx[i],yy=y+Dy[i];
			if(xx<=0||xx>n||yy<=0||yy>m||vis[xx][yy])
				continue;
			if(check(xx,yy))
				q.push({xx,yy}),vis[xx][yy]=1;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			pc(tag[i][j]?'.':'*');
		pc('\n');
	}
	return 0;
}\/\/\/woshishakou