CF1495C Garden of the Sun 做题记录

风见幽香的太阳花田是一个 $n\times m$ 的矩阵。

X 的位置是空地，. 的位置是向日葵，Imakf 保证给出的矩阵满足所有 X 两两之间的切比雪夫距离大于 $1$（没有公共点）。

请把一些 . 换成 X，使得所有的 X 四连通且不存在简单环（形成一棵树）。

$1\le n,m\le 500$。

不难想到由于题目对 $\texttt{X}$ 的个数没有限制，所以可以让某些行全都是 $\texttt{X}$ 来使得整张图联通。

首先相邻两行都全是 $\texttt{X}$ 肯定是不行的，空一行也不行，因为有如下情况：

XXXXXX
X  X X
XXXXXX

而由于原图满足任意两个 $\texttt{X}$ 没有公共边和公共顶点，所以如果我们空两行，肯定不会形成环。此时所有全是 $\texttt{X}$ 的行都和它上面和下面两行联通，而和其它行不连通：

XXXXXX
X   X
  X
XXXXXX

考虑合并这些联通块，显然只需要合并相邻的全为 $\texttt{X}$ 的行即可。由于原图满足任意两个 $\texttt{X}$ 没有公共顶点，所以只需要找到这两行之间有 $\texttt{X}$ 的一列，让这一列不为 $\texttt{X}$ 的位置也为 $\texttt{X}$ 即可。若找不到这样的列那么直接让第一列的两个位置都为 $\texttt{X}$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=505;

int n,m;
char a[S][S];

inline void slove()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
	for(int i=1+(n%3==0);i<=n;i+=3)
	{
		for(int j=1;j<=m;j++) a[i][j]='X';
		if(i+2<=n)
		{
			int pos=1;
			for(int j=2;j<=m;j++)
			{
				if(a[i+1][j]=='X'||a[i+2][j]=='X')
				{
					pos=j;
					break;
				}
			}
			a[i+1][pos]=a[i+2][pos]='X';
		}
	}
	for(int i=1;i<=n;i++) printf("%s\n",a[i]+1);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T-->0) slove();
	return 0;
}