「Solution」CF1586I Omkar and Mosaic
Liuxizai
·
·
题解
Description
现在一部分的格子颜色已经确定，判断是否存在合法的染色方案，以及合法方案是否唯一，如果存在唯一的合法方案，给出构造。
## Solution
Update：图片链接更换为了自己的图床。
> 图源 [Codeforces 官方题解](https://codeforces.com/blog/entry/96072)
是一道非常巧妙的构造题，虽然说是 CF 官方题解做法，但是在语言上结合了我自身的理解，一定程度上或许能够帮助各位理解。
首先，注意到最特殊的角块，角块需要与两个和其自身颜色相同的格子相邻，同时有且仅有两个格子与角块相邻，这意味着：
- I. 与角块相邻的两个格子与角块颜色相同。
同时还不难得出第二个结论：
- II. 对于一个不与网格边缘相邻的格子，其与四个格子相邻，故无论其自身是什么颜色，与它相邻的四个格子都应当是两黑两白。
结合 I. 与 II.，与主对角线相邻的两条对角线应当类似下图的进行黑白交替染色：
当 $n$ 为奇数时，我们将另一组类似的对角线也画出来：
这两组对角线出现了重合，对于一组对角线，我们要求其对应格子颜色相同，显然出现了矛盾，于是我们得出：$n$ 为奇数时不存在合法染色方案。
下一步，我们对于下图中的红色对角线应用 II.，
于是两条黄色对角线也应该按照类似的方式进行黑白交替染色。
重复上面的过程，我们可以将整个网格图进行这样的染色，
其中，颜色相同的对角线都应该进行黑白交替染色。（III.）
考虑下图中的黄色对角线：
对于两个与角块相邻的网格，它们已经与一个和自身颜色相同的网格相邻，这意味着另外两个与它们相邻的网格必须颜色不同。
于是，对于黄色对角线而言，它也应该进行黑白交替染色，这也意味着两端的两个黄色网格颜色相同。
进一步的，我们可以得出这样两个红色网格颜色也相同：
于是，这两条黄色对角线应当按照相同的方式黑白交替染色：
重复应用这一结论，我们可以发现一个合法的染色方案必然关于两条主对角线对称。
考虑下图中的两个红色网格：
对于与黄色对角线相邻的红色网格，其此时已经与两个不同颜色的网格相邻，这意味着两个红色网格颜色必然相同。
类似的，我们可以对网格边缘进行如下染色：
其中，相邻的一组黄色或红色网格应当被染上相同的颜色。
结合 III.，我们可以对整个网格进行如下染色：
其中，颜色相同的部分，在边缘处相邻的两个格子应当被染相同颜色，对角线部分应当进行黑白交替染色。
至此，题目的做法已经非常显然了，只需要将题目所给的所有限制映射至网格边缘，网格边缘的颜色一旦确定，整个网格的染色方案也就被确定了。
## Code
```cpp
namespace Main{
int n, g[N][N], color[N];
bool multi;
int readmp(){
char ch = getchar();
while(ch != '.' && ch != 'S' && ch != 'G') ch = getchar();
return ch == '.' ? 0 : (ch == 'S' ? 1 : 2);
}
void Main(){
input(n);
if(n & 1) return puts("NONE"), void();
for(ri i = 0; i < n; i++){
if(i & 1)
for(ri j = i, k = 0; j < n; j++, k++)
g[j][k] = (i >> 1) + 1;
else
for(ri j = i, k = 0; j >= 0; j--, k++)
g[j][k] = (i >> 1) + 1;
}
for(ri i = 0; i < n; i++){
for(ri j = 0; j < n; j++){
int tmp = readmp();
if(!tmp) continue;
if(bool(g[i][j]) ^ (~j&1)) tmp ^= 3;
if(color[g[i][j]|g[n-i-1][n-j-1]] &&
color[g[i][j]|g[n-i-1][n-j-1]] != tmp){
puts("NONE");
return;
}
color[g[i][j]|g[n-i-1][n-j-1]] = tmp;
}
}
multi = false;
for(ri i = 1; i <= n >> 1; i++) if(!color[i]) multi = true;
if(multi) return puts("MULTIPLE"), void();
puts("UNIQUE");
for(ri i = 0; i < n; i++){
for(ri j = 0; j < n; j++){
bool flag = false;
flag ^= color[g[i][j]|g[n-i-1][n-j-1]] == 1;
flag ^= bool(g[i][j]) ^ (~j&1);
putchar(flag ? 'S' : 'G');
}
puts("");
}
return;
}
} // namespace
```