题解：AT_arc214_f [ARC214F] Unpredictable Moves

Daniope1266 · 2026-08-10 14:52:35 · 题解

水题啊。

首先先不考虑不能连续两次向同一个方向移动这一条件，只是从左上到右下。

使用清朝 trick，问题可以视为让障碍不连通，如图：

但是不能连续走两格怎么办？

如左图所示：

可以证明这是充要条件，如右图所示：

曼哈顿距离 \le 2 的障碍互相连边，每个障碍拆成入点和出点，障碍间连边的话就是出点连向入点，然后最小割即可解决问题。

还是看代码吧：

int ID(int x,int y,bool t){
    return (x-1)*m+y+t*(n*m);
}
bool mp[105][105];
void SLV() {
    //墙左下->右上mincut
    ci2(n,m)
    W::s=2*n*m,W::t=2*n*m+1;
    FOR(n)FORj(m){
        char c;
        ci(c)
        mp[i][j]=(c=='#');
    }
    FOR(n)FORj(m)if(mp[i][j]){
        W::add(ID(i,j,0),ID(i,j,1),1);
    }
    /*
    曼哈顿距离<=2的墙需要干掉
    S->边墙0->墙1->边墙1->T
     INF    1   ...    INF
    */
    FOR(n)FORj(m)if(mp[i][j]){
        bool S=0,T=0;
        for(int dy=i-2;dy<=i+2;dy++)for(int dx=j-2;dx<=j+2;dx++){
            int d=abs(dy-i)+abs(dx-j);
            if(d==1||d==2){
                if(dy>=1&&dy<=n&&dx>=1&&dx<=m&&mp[dy][dx])W::add(ID(i,j,1),ID(dy,dx,0),INF);
                S|=(dy==0&&dx>=2);
                S|=(dy<=n-1&&dx==m+1);
                T|=(dy==n+1&&dx<=m-1);
                T|=(dy>=2&&dx==0);
            }
        }   
        if(S)W::add(W::s,ID(i,j,0),1);
        if(T)W::add(ID(i,j,1),W::t,1);
    }
    cr(W::ANS())
    W::CLEAR();
}