MENU

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
Last Modified: March 26, 2022
Archives Tip
QR Code for this page
Tipping QR Code