CF1667F 题解

· · 题解

\textbf{CF1667F *3500}

  • 给定 n \times m 的网格图，n,m 是 4 的倍数。有一些格子已经染上了红色、蓝色中的一种，有的格子还是空白。保证一个已经染色的格子周围八个格子没有别的已经染色的格子。

  • 给空白格子染色，使得所有蓝色格子四连通，所有红色格子四连通，或报告无解。

CF 上这题的 tag 只有 \text{implementation}。

0. 前言和约定

本题的另一篇题解存在一些小错误，且没有涉及太多细节。

这篇题解将详细的说明本题的各种细节。

所有图片中带 \texttt{\#} 的格子表示题目已经限定颜色，\texttt{x} 表示修改的位置。

1. 从边界空白出发

考虑本题的简单情况：保证边界格子都没有涂色。

这种情况下我们采用如下构造：

即，第一行涂红，最后一行涂蓝，对于行 i \in [2,n-1] 上的非 \texttt{\#} 格子，如果列 j \bmod 4 \le 1 涂蓝，否则涂红。以下我们称连续两个相同颜色的列为一个条纹，称第一行和最后一行为边线。

注意到 \texttt{\#} 格子不可能割断一个条纹，而条纹一定与边线连通，所以对于一个格子，它只要与条纹连通就一定在大连通块里。容易发现上述构造中，所有红色格子周围都有红色条纹，蓝色格子同理，那么上述构造合法。

2. 有解条件？

寻找一个合法的必要条件：边界上不能顺时针出现 \texttt{BWBW} 的子序列。这种情况下两个 \texttt{B} 连通后一定会割断两个 \texttt{W} 使其无法连通，故无解。

我们合理猜测这个条件也充分。下面直接给出构造。

下面请时刻记住，\texttt{BWBW} 的子序列已经不可能出现。

3. 给边界染色

对于边界上每一个 \texttt{\#}，顺时针把前面的每一个格子涂成相同的颜色，直到遇到下一个 \texttt{\#}，如下图。

（如果不存在 \texttt{\#} 则强行染红 (1,1)）

显然只会有不超过两个边界上会有两种颜色，我们一定能找到一个颜色全都相同的边界，且颜色不同的边界在对面。把这个边界放在最上面，后面可以省去一些讨论。

4. 让红色格子连通

我们不能完全按照 1 中方法涂色，但是大部分各自仍然可以这样涂。上面的边线我们可以全部涂红，红色条纹可以涂红，这样涂完红色格子都会连通，如下图。

此后，蓝色格子会出现三种不连通情况。

5. 处理下方边线

这种情况下会出现较多情况，第一种即上图，格子 (8,3),(8,4),(7,3),(7,4) 形成一个 X 形让蓝色区域不连通。此时我们直接修改底边那个不是 \texttt{\#} 的格子，例如上图就翻转 (8,4) 将其变成蓝色。

另外两种情况及处理方式如图：

注意右边可能会出现类似情况，处理方式大体相同。请注意左右不会同时出现这种情况，否则就会出现 \texttt{BWBW}。

这一段代码如下：

    //a 是正在涂色的数组，lim 是原来的网格。
    int fi = 1e9,lt = 0;
    for(int i = 1;i <= m;i ++) if(a[n][i] == Y) fi = min(fi,i),lt = i;
    if(fi == 1e9 || fi < m-2 && lt > 3);
    else if(lt <= 3 && a[n-1][4] == X) a[n][3] = a[n][4] = a[n][5] = Y;
    else if(fi >= m - 2 && a[n-1][m-3] == X) a[n][m-2] = a[n][m-3] = a[n][m-4] = Y;
    else{
        int p = (lt <= 3 ? 2 : m - 2); 
        for(int i = p;i <= p + 1;i ++) for(int j = n - 1;j <= n;j ++)
            if(!lim[j][i]) a[j][i] = Y;
    }

这样两边的蓝条纹就会和蓝边线连通。

6. 处理孤立蓝色

因为最后一列和第一列没有完全填蓝，所以第 2,m-2 列会出现孤立蓝色，大概有这四种情况。基本思路是打穿红色块，和中间蓝色条纹连通。注意保持红色连通。

这样以后蓝色孤立点消失，这一部分代码如下。

    for(int i = 2;i < n;i ++) if(a[i][2] == Y  && a[i-1][2] == X && a[i+1][2] == X && a[i][1] == X && a[i][3] == X) 
        if(i != n - 1 && a[i+2][1] == Y) a[i][1] = a[i+1][1] = Y;
        else if(a[i-2][2] == Y) a[i-1][2] = Y; 
        else if(a[i][4] != X && lim[i][3] != X) a[i][3] = Y;
        else if(i != 2 && a[i-1][4] != X) a[i-1][2] = a[i-1][3] = Y;
        else a[i+1][2] = a[i+1][3] = Y;
    for(int i = 2;i < n;i ++) if(a[i][m-1] == Y && a[i-1][m-1] == X && a[i+1][m-1] == X&& a[i][m] == X && a[i][m-2] == X) 
        if(i != n - 1 && a[i+2][m] == Y) a[i][m] = a[i+1][m] = Y;
        else if(a[i-2][m-1] == Y) a[i-1][m-1] = Y; 
        else if(a[i][m-3] != X && lim[i][m-2] != X) a[i][m-2] = Y;
        else if(i != 2 && a[i-1][m-3] != X) a[i-1][m-1] = a[i-1][m-2] = Y;
        else a[i+1][m-1] = a[i+1][m-2] = Y;

7. 连接蓝色条纹

多个蓝色条纹之间可能不连通。

请注意情况二中，一定要红色补在上面，蓝色涂在下面，因为 (5,5) 格子如果是蓝色障碍，填反了红色会不连通。（WA on test 17 可能是因为这个）

这一部分代码如下。

    auto con = [&](int x){
        for(int i = 2;i <= 4;i ++)
            if(lim[i][x-1] != X && lim[i][x] != X && lim[i][x+1] != X && lim[i][x+2] != X)
                return a[i][x] = a[i][x + 1] = Y,void();
        for(int i = x - 1;i <= x + 2;i ++) if(lim[3][i] != X) a[3][i] = Y;
        if(lim[3][x - 1] == X) a[4][x] = Y,a[2][x - 1] = X;
        if(lim[3][x + 2] == X) a[4][x + 1] = Y,a[2][x + 2] = X;
        if(lim[3][x] == X || lim[3][x + 1] == X) a[2][x] = a[2][x + 1] = Y;
    };
    for(int i = 6;i <= m - 6;i += 4) if(a[n][i] == X || a[n][i + 1] == X) con(i);

8. 完整代码

/**
 *    author: sunkuangzheng
 *    created: 26.02.2024 14:32:14
**/
#include<bits/stdc++.h>
#ifdef DEBUG_LOCAL
#include <mydebug/debug.h>
#endif
using ll = long long;
const int N = 2e3+5;
using namespace std;
int T,n,m,a[N][N],b[N][N],rott,lim[N][N],c[N][N],tc,fkfg; string s[N];
void los(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++) cin >> s[i],s[i] = " " + s[i];
    for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++)
        a[i][j] = (s[i][j] == 'W' ? 1 : (s[i][j] == 'B' ? 2 : 0)),lim[i][j] = a[i][j];
    auto around = [&]{
        vector<int> fk; int cnt = 0;
        for(int _ = 1;_ <= 2;_ ++){
            for(int i = 2;i <= m;i ++) if(!a[1][i]) a[1][i] = a[1][i-1];
            for(int i = 2;i <= n;i ++) if(!a[i][m]) a[i][m] = a[i-1][m];
            for(int i = m - 1;i >= 1;i --) if(!a[n][i]) a[n][i] = a[n][i+1];
            for(int i = n - 1;i >= 1;i --) if(!a[i][1]) a[i][1] = a[i+1][1];
            if(!a[1][1]) a[1][1] = 1;
        }for(int i = 1;i <= m;i ++) fk.push_back(a[1][i]);
        for(int i = 1;i <= n;i ++) fk.push_back(a[i][m]);
        for(int i = m;i >= 1;i --) fk.push_back(a[n][i]);
        for(int i = n;i >= 1;i --) fk.push_back(a[i][1]);
        for(int i = 1;i < fk.size();i ++) cnt += (fk[i] != fk[i - 1]);
        return cnt;
    };auto rot = [&](){
        for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++) b[i][j] = a[i][j],c[i][j] = lim[i][j];
        for(int i = 1;i <= n;i ++) for(int j = 1;j <= m;j ++) a[j][n - i + 1] = b[i][j],lim[j][n - i + 1] = c[i][j];
        ++ rott,swap(n,m);
    };auto ck = [&](){
        int fg = 0;
        for(int i = 1;i <= m;i ++){
            if(a[1][i] != a[1][1]) return 0;
            fg |= (i > 1 && i < m && a[1][i] != a[n][i]);
        }return fg;
    }; int ti = around();
    if(ti >= 3) return cout << "NO\n",void();
    cout << "YES\n";
    if(ti) while(!ck()) rot();
    int X = a[1][1],Y = 3 - a[1][1];
    for(int i = 2;i < n;i ++) for(int j = 2;j < m;j ++)
        if(!lim[i][j]) a[i][j] = (j % 4 > 1 ? X : Y);
    for(int i = 1;i < m;i ++)
        if(a[n][i] == a[n-1][i+1] && a[n-1][i] == a[n][i+1] && a[n][i] != a[n][i+1])
            if(!lim[n][i]) a[n][i] = 3 - a[n][i]; else a[n][i+1] = 3 - a[n][i+1];
    int fi = 1e9,lt = 0;
    for(int i = 1;i <= m;i ++) if(a[n][i] == Y) fi = min(fi,i),lt = i;
    if(fi == 1e9 || fi < m-2 && lt > 3);
    else if(lt <= 3 && a[n-1][4] == X) a[n][3] = a[n][4] = a[n][5] = Y;
    else if(fi >= m - 2 && a[n-1][m-3] == X) a[n][m-2] = a[n][m-3] = a[n][m-4] = Y;
    else{
        int p = (lt <= 3 ? 2 : m - 2); 
        for(int i = p;i <= p + 1;i ++) for(int j = n - 1;j <= n;j ++)
            if(!lim[j][i]) a[j][i] = Y;
    }for(int i = 2;i < n;i ++) if(a[i][2] == Y  && a[i-1][2] == X && a[i+1][2] == X && a[i][1] == X && a[i][3] == X) 
        if(i != n - 1 && a[i+2][1] == Y) a[i][1] = a[i+1][1] = Y;
        else if(a[i-2][2] == Y) a[i-1][2] = Y; 
        else if(a[i][4] != X && lim[i][3] != X) a[i][3] = Y;
        else if(i != 2 && a[i-1][4] != X) a[i-1][2] = a[i-1][3] = Y;
        else a[i+1][2] = a[i+1][3] = Y;
    for(int i = 2;i < n;i ++) if(a[i][m-1] == Y && a[i-1][m-1] == X && a[i+1][m-1] == X&& a[i][m] == X && a[i][m-2] == X) 
        if(i != n - 1 && a[i+2][m] == Y) a[i][m] = a[i+1][m] = Y;
        else if(a[i-2][m-1] == Y) a[i-1][m-1] = Y; 
        else if(a[i][m-3] != X && lim[i][m-2] != X) a[i][m-2] = Y;
        else if(i != 2 && a[i-1][m-3] != X) a[i-1][m-1] = a[i-1][m-2] = Y;
        else a[i+1][m-1] = a[i+1][m-2] = Y; 
    auto con = [&](int x){
        for(int i = 2;i <= 4;i ++)
            if(lim[i][x-1] != X && lim[i][x] != X && lim[i][x+1] != X && lim[i][x+2] != X)
                return a[i][x] = a[i][x + 1] = Y,void();
        for(int i = x - 1;i <= x + 2;i ++) if(lim[3][i] != X) a[3][i] = Y;
        if(lim[3][x - 1] == X) a[4][x] = Y,a[2][x - 1] = X;
        if(lim[3][x + 2] == X) a[4][x + 1] = Y,a[2][x + 2] = X;
        if(lim[3][x] == X || lim[3][x + 1] == X) a[2][x] = a[2][x + 1] = Y;
    };
    for(int i = 6;i <= m - 6;i += 4) if(a[n][i] == X || a[n][i + 1] == X) con(i);
    while(rott % 4) rot(); rott = 0;
    for(int i = 1;i <= n;i ++,cout << "\n") for(int j = 1;j <= m;j ++)
        cout << (a[i][j] == 1 ? 'W' : 'B');
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(cin >> T;T --;) los();
}

9. 一些数据

都是我 WA 过的，如果上面哪个情况讨论漏了，这些数据可能能帮你查出来。

8
8 8
.....B.B
B.W.....
.....W..
.W.W...B
........
.B....W.
...B....
.W...B.B
8 8
.W.W....
.....B.W
.W.W....
.....W.W
B.B.....
....B.B.
B.W.....
....B.B.
8 8
....B.W.
B.W.....
....B..W
..B.....
B...B.W.
........
.B.W.W.W
........
8 8
....B..B
.W......
...W.W..
.......B
W..W.W..
.......W
.B.B.B..
.......W
8 8
...W.W..
.W.....W
....W...
B.W....B
....B...
.W......
...W.W.B
.B......
8 8
.......W
.B.W.B..
........
W.B..B.W
........
B.B.B.W.
........
.B..B.W.
8 12
.B.B........
......W..W.B
B...W.......
..W.....W.B.
B....W......
...B...B....
.W........W.
....B.W.W...
8 12
B.W.........
......B.W...
W..B......B.
........W...
...W.W....W.
.W.....W....
...B.W....W.
............

上面的数据全都有解。

其实把各种情况讨论清楚后，本题也并不是特别难写啦！

我就调了一个下午一个晚上和半个上午就过了！！！111