思路
实际上，如果你会简单版本，那么困难版本也没有那么难了。
同样考虑构造一种通解，如下，
红色的格子改为 X，绿色的格子改为 O，就是一种通解，同样的，这样改可能会超过棋子总数的 \(\frac 1 3\)。
同样考虑将棋子按照位置分类，假如该棋子的位置是 \((i,j)\)，那么按照 \((i+j)\bmod 3\) 的值分类即可，将值为 \(0\) 的看作第 \(0\) 类，值为 \(1\) 的看作第 \(1\) 类，将值为 \(2\) 的看作第 \(2\) 类。
显然的是，将所有第 \(0\) 类棋子改为 X，所有第 \(1\) 类棋子改为 O 是一种方案，还有将第 \(1\2\) 类棋子改为 X，所有第 \(2\3\) 类棋子改为 O 两种方案，总共三种方案，所需要更改的棋子数是将所有棋子全部改完所需要的次数。
根据抽屉原理，三种方案必定至少有一种方案需要的次数少于总棋子数的 \(\frac 1 3\)，所以分别统计需要更改个数，最后随意选择一种合理的方案更改即可。
AC code
#include<bits/stdc++.h>
using namespace std;
int T,n,numx[3],numo[3],sum,xz;
char ch[305][305];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n),sum=numx[0]=numx[1]=numx[2]=numo[0]=numo[1]=numo[2]=0;
for(int i=1;i<=n;++i)
{
scanf("%s",ch[i]+1);
for(int j=1;j<=n;++j)
{
if(ch[i][j]=='O') ++numo[(i+j)%3],++sum;
if(ch[i][j]=='X') ++numx[(i+j)%3],++sum;//记录每种方案需要更改的棋子数
}
}
if(numx[0]+numo[1]<=sum/3) xz=0;
if(numx[1]+numo[2]<=sum/3) xz=1;
if(numx[2]+numo[0]<=sum/3) xz=2;//判断使用那种方法
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(ch[i][j]=='.') printf(".");
else
{
if((i+j)%3!=xz&&(i+j)%3!=(xz+1)%3) printf("%c",ch[i][j]);
else
{
if((i+j)%3==xz) printf("O");
else printf("X");
}//对应更改即可
}
}
puts("");
}
}
return 0;
}