CF1586I 题解
简化题意：有 $n\times n$ 的网格，你需要进行黑白染色，使得每个格子的颜色恰好与 2 个与其四联通的格子的颜色相同，其中有些位置已经确定，问是否有解及是否有唯一解。
思路：
很神仙的构造题。
先从特殊的地方入手。对于 4 个角，它们只和 2 个格子相邻，因此颜色也必须相同。接着考虑与主对角线相邻的两条对角线，我们可以从边界上入手，边界上的两个格子颜色必须相同，而对于主对角线上的第二个格子，现在已经有两个相邻格子是一个颜色了，因此剩下的两个格子颜色一定与刚刚的两个格子不同，于是可以推出这两条对角线上的格子的颜色是黑白交替的，如下图（图都是搬运自 CF 官方题解 ）：
考虑到这和奇偶性有关，可以分析一下 $n$ 的奇偶性。发现当 $n$ 为奇数时，主、副对角线相邻的各两条对角线会在中心的边上重合，但是两边都得是黑黑白交替的，无法同时满足，因此必然无解。
接着考虑另一个方向的对角线，如下图的黄色部分：
对于在左边界上的蓝色格子，我们已经知道它下面的格子和它一个颜色了，因此与它相邻的两个黄色格子颜色一定不同，于是可以推出黄色的格子颜色也是黑白交替的。又因为这条对角线的长度是奇数，因此在边界上的两个格子颜色相同。而这两个格子颜色相同也可以推出下图中红色格子颜色相同：
于是可以推出两个红色的格子所在对角线是相同的，且都是黑白交替的：
这样不断拓展下去可以推出整个图形是关于主、副对角线对称的。
然后是关键一步：对于下图中上面那个红色格子，与其相邻的两个黄色格子只会有一个的颜色与它相同，于是下面的格子也一定是红色，
那么继续拓展下去可以知道，我们把边界上的格子两两一组，每一组格子的颜色一定相同：
再根据之前与对角线相关的结论，我们可以知道每一组格子会对应哪些对角线，于是我们就知道了每个格子会影响哪些格子：
具体地，对于相同颜色的格子，在边界上黑白应该相同，在对角线上应该黑白交替。这样我们相当于是把每个格子的限制转到了对边界的限制，于是我们就很容易求出答案了。
代码：
点击查看代码
inline void solve(){
cin>>n;
for(int i=0;i<n;i++)cin>>c[i];
if(n&1){
cout<<"NONE";
return;
}
for(int i=0;i<n;i++){
if(i&1){
for(int j=i;j<n;j++)id[j][j-i]=id[j-i][j]=id[n-1-j][n-1-(j-i)]=id[n-1-(j-i)][n-1-j]=i^1;
}
else for(int j=i;~j;j--)id[j][i-j]=id[i-j][j]=id[n-1-j][n-1-(i-j)]=id[n-1-(i-j)][n-1-j]=i;
}
memset(ans,-1,sizeof(ans));
for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(c[i][j]!='.'){
bool fl=c[i][j]=='G';
if(i&&i<n-1&&j&&j<n-1)fl^=(min({i,j,n-1-i,n-1-j})&1);
if(!~ans[id[i][j]])ans[id[i][j]]=fl;
else if(ans[id[i][j]]!=fl){
cout<<"NONE"<<endl;
return;
}
}
for(int i=0;i<n;i+=2)if(!~ans[i]){
cout<<"MULTIPLE"<<endl;
return;
}
cout<<"UNIQUE"<<endl;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
bool fl=ans[id[i][j]];
if(i&&i<n-1&&j&&j<n-1)fl^=(min({i,j,n-1-i,n-1-j})&1);
cout<<(fl?'G':'S');
}
cout<<endl;
}
}