[CF1495C] Garden of the Sun

前言

虚拟赛。D WA了九发，靠二十多分钟切掉这道题翻盘。

题目

CF

洛谷

题目大意：

(t) 组数据，每组数据给一个 (n) 行 (m) 列的矩阵，其中只包含 X 与 .。你需要把 . 改成 X，使得所有的 X 构成一棵树。

保证初始的 X 两两没有公共点。

(1le tle 10^4;1le n,mle 500;sum ncdot mle 250000.)

讲解

直接给出方法：

每空两行全部变成 X 。显然此时没有环，但也不联通，大概长这个样子：

然后我们把每相邻两行之间都挑一个突出的枝头使上下连起来：

注意不要忘了最下面可能会有单点，以及每相邻两行之间没有枝头的情况。

此时显然连通，而且由于初始 X 两两没有公共点，所以也不会出现环。

代码

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	for(int T = Read(); T ;-- T)
	{
		n = Read(); m = Read();
		for(int i = 1;i <= n;++ i) scanf("%s",a[i]+1);
		for(int i = 1;i <= n;i += 3)
			for(int j = 1;j <= m;++ j) a[i][j] = 'X';
		if((n-1) % 3 == 2)
			for(int j = 1;j <= m;++ j)
				if(a[n][j] == 'X') a[n-1][j] = 'X';
		for(int i = 2;i <= n;i += 3)
		{
			bool f = 1;
			for(int j = 1;j <= m && f;++ j)
				if(a[i][j] == 'X')
				{
					f = 0;
					a[i+1][j] = 'X';
				}
			if(i+1 > n) break;
			for(int j = 1;j <= m && f;++ j)
				if(a[i+1][j] == 'X')
				{
					f = 0;
					a[i][j] = 'X';
				}
			if(f) a[i][1] = a[i+1][1] = 'X';
		}
		for(int i = 1;i <= n;++ i,putchar('
'))
			for(int j = 1;j <= m;++ j)
				putchar(a[i][j]);
	}
	return 0;
}