题解 CF1567F【One-Four Overload】

· · 题解

这里首先把与某个被标记的格子相邻的未被标记的格子数量记作这个格子的度数。我们分别考虑度数为 0 到 4 的格子。

如果没有度数为 4 的格子，我们可以把每个格子当作一个点，然后对于所有度数为 2 的格子，把与它相邻的两个未被标记的格子连边，跑一遍二分图染色，直接做就行了。

这里我们可以发现，这样连出来的图一定是二分图。尝试反证，假设我们连出来了一个奇环，首先环上会出现两类边，第一类是直着连的，例如连接 (x,y) 和 (x+2,y)，第二类是连接对角线的，例如连接 (x,y) 和 (x+1,y+1)。第二类边一定会出现偶数个，否则连不成环，因此这里只需要考虑第一类边。

环在网格上会围成一个简单多边形。对于每个第一类边，都会对应一个标记过的格子，并且这个格子在多边形内外各有一个相邻的标记过的格子。根据题目已知信息，每个被标记的格子度数都是偶数，因此每个连通块中，被标记的格子对应的点可以形成一个欧拉回路。这个欧拉回路一定是会进出这个多边形若干次，假定这个回路从多边形外出发，那么它最终一定会回到多边形外，反之亦然。但是如果第一类边只有奇数个，那么在多边形上的点也只有奇数个，这里我们暂时先假设这些点处于同一连通块。但是由于每个在多边形上的点只能经过一次，因此从多边形外出发，无法回到多边形外，欧拉回路不存在，与实际情况矛盾。所以没有奇环。

上面的证明假设了这些点处于同一连通块的情况，还需要考虑这些点处于不同连通块的情况，不过其实都是一样的，每个连通块会用掉偶数个点，本质还是奇偶性不满足。

接下来考虑把度数为 4 的格子加入，总共有两种情况，图 1 的对位填的数相同和图 2 的邻位填的数相同。

这样看起来不太可做，但实际上，加上度数为 4 的格子之后还是一定有解，并且一定存在一种方案，使得所有度数为 4 的格子周围的格子都以图 1 的方式（即相对的两个格子数字相同）填数。这样我们就可以像下图方式一样连边。

连完之后，同样可以证明，最后的图还是一个二分图。因此这样连边虽然让限制更加严格了，但是仍然保证能求出一组解。

说到这里也差不多了，下面是代码：
写得比较丑。。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ec = 0,to[1000005],nxt[1000005],hed[250005],col[250005];
ll n,m,flg;
char ch[505][505];
void add_edge(ll f,ll t){
    ++ ec; to[ec] = t; nxt[ec] = hed[f]; hed[f] = ec;
    ++ ec; to[ec] = f; nxt[ec] = hed[t]; hed[t] = ec;
}

void dfs(ll u){
    for(ll v,i = hed[u];i;i = nxt[i]){
        v = to[i];
        if(col[v]) continue;
        col[v] = 5 - col[u];
        dfs(v);
    }
}

ll get_id(ll x,ll y){
    return (x - 1) * m + y;
}

int main(){
    ios::sync_with_stdio(false);
    flg = 1;
    cin >> n >> m;
    for(ll i = 1;i <= n;i ++){
        for(ll j = 1;j <= m;j ++){
            cin >> ch[i][j];
        }
    }
    for(ll i = 2;i < n;i ++){
        for(ll tmp,tu,tv,j = 2;j < m;j ++){
            if(ch[i][j] != 'X') continue;
            tmp = (ch[i - 1][j] == 'X') + (ch[i][j - 1] == 'X') + (ch[i + 1][j] == 'X') + (ch[i][j + 1] == 'X');
            if(tmp == 1 || tmp == 3) flg = 0;
            if(tmp == 0){
                add_edge(get_id(i - 1,j),get_id(i,j - 1));
                add_edge(get_id(i - 1,j),get_id(i,j + 1));
                add_edge(get_id(i + 1,j),get_id(i,j - 1));
                add_edge(get_id(i + 1,j),get_id(i,j + 1));
            }
            if(tmp == 2){
                tu = tv = -1;
                if(ch[i - 1][j] == '.'){
                    if(tu == -1) tu = get_id(i - 1,j);
                    else tv = get_id(i - 1,j);
                }
                if(ch[i][j - 1] == '.'){
                    if(tu == -1) tu = get_id(i,j - 1);
                    else tv = get_id(i,j - 1);
                }
                if(ch[i + 1][j] == '.'){
                    if(tu == -1) tu = get_id(i + 1,j);
                    else tv = get_id(i + 1,j);
                }
                if(ch[i][j + 1] == '.'){
                    if(tu == -1) tu = get_id(i,j + 1);
                    else tv = get_id(i,j + 1);
                }
                add_edge(tu,tv);
            }
        }
    }
    if(!flg){
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for(ll u,i = 1;i <= n;i ++){
        for(ll j = 1;j <= m;j ++){
            if(ch[i][j] == 'X') continue;
            u = get_id(i,j);
            if(!col[u]){
                col[u] = 1;
                dfs(u);
            }
        }
    }
    for(ll i = 1;i <= n;i ++){
        for(ll tmp,j = 1;j <= m;j ++){
            tmp = (ch[i - 1][j] == 'X') + (ch[i][j - 1] == 'X') + (ch[i + 1][j] == 'X') + (ch[i][j + 1] == 'X');
            if(ch[i][j] == 'X') cout << ((4 - tmp) >> 1) * 5;
            else cout << col[get_id(i,j)];
            cout << (j == m ? '\n' : ' ');
        }
    }
    return 0;
}