再不写题解社贡要掉到 \(0\) 了。
题目分析
显然如果 \(3\) 个格子构成了满足获胜条件的情况，这 \(3\) 个格子模 \(3\) 的余数各不相同。
那么我们将格子按模 \(3\) 的余数分为 \(3\) 类，只要保证相邻 \(3\) 个格子中有 \(2\) 个不同就行了，不需要动第 \(3\) 个。
我们令格子数最多的类型为 . 而其余为 X 和 O，显然 . 的个数不少于总数的 \(\dfrac{1}{3}\)。
剩下有 \(2\) 种情况，分别是第 \(1\) 类 X、第 \(2\) 类 O 和第 \(1\) 类 O、第 \(2\) 类 X，它们操作次数的总和一定是 X 和 O 的数量之和。根据抽屉原理，一定有一种情况操作不超过 \(\lfloor \dfrac{k}{3} \rfloor\)
贴上代码
// Problem: Errich-Tac-Toe (Hard Version)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1450C2
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
// #define int long long
#define ok puts("First")
#define no puts("Second")
#define debug puts("Shima_Rin_kawaii")
#define clean fflush(stdout)
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
return x*f;
}
const int maxn=310;
int n;
int res;
int a[5];
char s[maxn][maxn],ans[maxn][maxn];
inline void init(){
n=read();res=0;
memset(a,0,sizeof(a));
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n;++j) cin>>s[i][j];
}
}
inline void solve(){
init();
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n;++j){
if(s[i][j]=='X') a[(i+j)%3]++;
else if(s[i][j]=='O') a[(i+j-1)%3]++;
}
}
for(register int i=0;i<3;++i){
if(a[i]<=a[res]) res=i;
}
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n;++j){
if(s[i][j]=='X'&&(i+j)%3==res) ans[i][j]='O';
else if(s[i][j]=='O'&&(i+j-1)%3==res) ans[i][j]='X';
else ans[i][j]=s[i][j];
}
}
for(register int i=1;i<=n;++i){
for(register int j=1;j<=n;++j) cout<<ans[i][j];
puts("");
}
}
int main(){
// freopen("test.out","w",stdout);
int T=read();
while(T--) solve();
}