CF1450C2 Errich-Tac-Toe (Hard Version) 做题记录

给定一张 $n$ 行 $n$ 列的棋盘，每个格子可能是空的或包含一个标志，标志有 $\text{X}$ 和 $\text{O}$ 两种。

如果有三个相同的标志排列在一行或一列上的三个连续的位置，则称这个棋盘是一个 胜局，
否则称其为 平局。

例如，上图第一行的局面都是胜局，而第二行的局面都是平局。

在一次操作中，你可以将一个 $\text X$ 改成 $\text O$，或将一个 $\text O$ 改成 $\text X$。

设棋盘中标志的总数为 $k$，你需要用不超过 $\lfloor \frac{k}{3}\rfloor$
次操作把给定的局面变成平局。

$1\leq n\leq 300$。

看到 $\lfloor\frac{k}{3}\rfloor$ 和 $3$ 子棋就很容易想到抽屉原理，那么考虑把所有格子 $(i,j)$ 按照 $(i+j)\mod 3$ 分成三类。

不难发现，若 $0\le x<3,0\le y<3,x\not=y$，那么只要所有格子满足以下条件：

• 满足 $(i+j)\mod 3=x$ 的有棋子的格子都为 $\texttt{X}$；
• 满足 $(i+j)\mod 3=y$ 的有棋子的格子都为 $\texttt{O}$；

就可以使局面为平局，因为同一行上或同一列上相邻三个棋子的分类一定不同。

那么枚举 $x,y$ 即可，不难发现有 $6$ 种情况，所有情况的操作总次数为 $2k$。那么由于抽屉原理 $\lfloor\frac{2k}{6}\rfloor=\lfloor\frac{k}{3}\rfloor$，所以一定有一种情况合法。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=305;

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

inline int work(int tp1,int tp2)
{
	int tot=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=n+1;j++) b[i][j]=a[i][j];
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int id=(i+j)%3;
			if(a[i][j]=='X'&&id==tp1) tot++,b[i][j]='O';
			if(a[i][j]=='O'&&id==tp2) tot++,b[i][j]='X';
		}
	}
	return tot;
}

inline void print()
{
	for(int i=1;i<=n;i++) printf("%s\n",b[i]+1);
}

inline void slove()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%s",a[i]+1);
	int k=0;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) k+=a[i][j]!='.';
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			if(i==j) continue;
			if(work(i,j)<=k/3)
			{
				print();
				return;
			}
		}
	}
}

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