【CF525D】Arthur and Walls

题目

题目链接：https://codeforces.com/problemset/problem/525/D
给出一个 (n imes m) 的矩阵，里面有 * 和 . 两种符号，要求把最少的 * 变成 .，使得 . 的联通块构成一个矩形。求最少需要变几个 *。

思路

如果一个由 . 构成的连通块是一个矩形，那么这个连通块内任意的一个子矩形都是由 . 构成的。
所以说我们只需要判断每一个 (2 imes 2) 的子矩形，如果这个子矩形中有 (3) 个 .，那么就把剩下的一个 * 变成 .。
拓扑排序即可。
时间复杂度 (O(nm))。

代码

#include <bits/stdc++.h>
#define mp make_pair
using namespace std;

const int N=2010;
const int dx[9]={0,-1,1,-1,1,-1,1,0,0},dy[9]={0,-1,1,1,-1,0,0,-1,1};
int n,m;
char ch[N][N];
queue<pair<int,int> > q;

void check(int i,int j)
{
	bool flag=0;
	if (ch[i-1][j]=='.' && ch[i][j-1]=='.' && ch[i-1][j-1]=='.') flag=1;
	if (ch[i-1][j]=='.' && ch[i][j+1]=='.' && ch[i-1][j+1]=='.') flag=1;
	if (ch[i+1][j]=='.' && ch[i][j-1]=='.' && ch[i+1][j-1]=='.') flag=1;
	if (ch[i+1][j]=='.' && ch[i][j+1]=='.' && ch[i+1][j+1]=='.') flag=1;
	if (flag) q.push(mp(i,j)),ch[i][j]='.';
}

void topsort()
{
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			if (ch[i][j]=='*') check(i,j);
	while (q.size())
	{
		int x=q.front().first,y=q.front().second;
		q.pop();
		for (int k=1;k<=8;k++)
		{
			int i=x+dx[k],j=y+dy[k];
			if (ch[i][j]=='*') check(i,j);
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			while (ch[i][j]=getchar())
				if (ch[i][j]=='.' || ch[i][j]=='*') break;
	topsort();
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
			putchar(ch[i][j]);
		putchar(10);
	}
	return 0;
}