Solution. CF1586I Omkar and Mosaic

Description

$n\times n$ 的网格，你需要对所有格子进行黑白染色，对于每个格子，需保证与其相邻的格子中恰有 $2$ 个与其颜色相同。

现在一部分的格子颜色已经确定，判断是否存在合法的染色方案，以及合法方案是否唯一，如果存在唯一的合法方案，给出构造。

Solution

图源 Codeforces 官方题解

是一道非常巧妙的构造题，虽然说是 CF 官方题解做法，但是在语言上结合了我自身的理解，一定程度上或许能够帮助各位理解。

首先，注意到最特殊的角块，角块需要与两个和其自身颜色相同的格子相邻，同时有且仅有两个格子与角块相邻，这意味着：

I. 与角块相邻的两个格子与角块颜色相同

同时还不难得出第二个结论：

II. 对于一个不与网格边缘相邻的格子，其与四个格子相邻，故无论其自身是什么颜色，与它相邻的四个格子都应当是两黑两白

结合 I. 与 II.，与主对角线相邻的两条对角线应当类似下图的进行黑白交替染色：

当 $n$ 为奇数时，我们将另一组类似的对角线也画出来：

这两组对角线出现了重合，对于一组对角线，我们要求其对应格子颜色相同，显然出现了矛盾，于是我们得出：$n$ 为奇数时不存在合法染色方案。

下一步，我们对于下图中的红色对角线应用 II.，

于是两条黄色对角线也应该按照类似的方式进行黑白交替染色。

重复上面的过程，我们可以将整个网格图进行这样的染色，

其中，颜色相同的对角线都应该进行黑白交替染色。（III.）

考虑下图中的黄色对角线：

对于两个与角块相邻的网格，它们已经与一个和自身颜色相同的网格相邻，这意味着另外两个与它们相邻的网格必须颜色不同。

于是，对于黄色对角线而言，它也应该进行黑白交替染色，这也意味着两端的两个黄色网格颜色相同。

进一步的，我们可以得出这样两个红色网格颜色也相同：

于是，这两条黄色对角线应当按照相同的方式黑白交替染色：

重复应用这一结论，我们可以发现一个合法的染色方案必然关于两条主对角线对称。

考虑下图中的两个红色网格：

对于与黄色对角线相邻的红色网格，其此时已经与两个不同颜色的网格相邻，这意味着两个红色网格颜色必然相同。

类似的，我们可以对网格边缘进行如下染色：

其中，相邻的一组黄色或红色网格应当被染上相同的颜色。

结合 III.，我们可以对整个网格进行如下染色：

其中，颜色相同的部分，在边缘处相邻的两个格子应当被染相同颜色，对角线部分应当进行黑白交替染色。

至此，题目的做法已经非常显然了，只需要将题目所给的所有限制映射至网格边缘，网格边缘的颜色一旦确定，整个网格的染色方案也就被确定了。

Code

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

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Catalog

Solution. CF1586I Omkar and Mosaic

Description

Solution

Code