Solution P11972 [JOI Open 2020] 家具摆放 / Furniture

· · 题解

对于这种题，一个常见的 trick 是考虑最上方和最下方的两条路径。

发现修改后不合法当且仅当修改点在两条路径的并上。考虑动态维护两条路径。

以维护最靠上路径为例（最靠下同理），考虑删去点的影响。

记 d(i,j) 表示是否能从 (i,j) 到 (n,m)。考虑从删除点往左上角 bfs 找出会修改哪些点的 d(i,j)。由于 d(i,j) 只会从 1 变 0，因此直接做是 O(nm) 的。

发现答案路径上的一个区间被修改了，找出左端点后一直往下搜出新路径和右端点，然后删去原来路径即可。由于一个点只会加入路径和从路径删除一次，因此这部分还是 O(nm) 的。

时间复杂度 O(nm)。

// Code by UniGravity
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define forto(i,a,b) for(int i=(a),_##i(b);i<=_##i;i++)
#define forbk(i,a,b) for(int i=(a),_##i(b);i>=_##i;i--)
#define forv(i,a) for(int i(0),_##i(a);i<_##i;i++)
#define fst first
#define snd second
#define il inline
#define eb emplace_back
#define mkp make_pair
using namespace std;
il int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||'9'<c)c=='-'?(f=-1):0,c=getchar();
    while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N=1005;
int n,m,q;

struct Path{
    bool tmp;
    int n,m,a[N][N];
    bool bk[N][N],pth[N][N];
    il void paint(){
        if(!tmp)return;
        cerr<<"------------------------------------------------\n";
        forto(i,1,n){
            forto(j,1,m)cerr<<a[i][j];
            cerr<<"  ";
            forto(j,1,m)cerr<<bk[i][j];
            cerr<<"  ";
            forto(j,1,m)cerr<<pth[i][j];
            cerr<<'\n';
        }
    }
    il void dfs(int x,int y){
        pth[x][y]=1;
        if(x==n&&y==m)return;
        if(bk[x][y+1])dfs(x,y+1);else dfs(x+1,y);
    }
    il void init(){
        bk[n][m]=1;
        forbk(i,n,1)forbk(j,m,1){
            if((i==n&&j==m)||a[i][j])continue;
            bk[i][j]=bk[i][j+1]||bk[i+1][j];
        }
        dfs(1,1);
        paint();
    }
    il pii dfs2(int x,int y){
        if(pth[x][y])return mkp(x,y);
        pth[x][y]=1;
        if(bk[x][y+1])return dfs2(x,y+1);else return dfs2(x+1,y);
    }
    pii ed;
    il void dfs3(int x,int y){
        pth[x][y]=0;
        if(mkp(x,y)==ed)return;
        if(pth[x-1][y])dfs3(x-1,y);else dfs3(x,y-1);
    }
    queue<pii>q;
    il void del(int x,int y){
        q.push(mkp(x-1,y)),q.push(mkp(x,y-1));
        a[x][y]=1,bk[x][y]=0;
        vector<pii>node;
        while(!q.empty()){
            int u=q.front().first,v=q.front().second;q.pop();
            if(u<1||v<1||!bk[u][v]||a[u][v])continue;
            bk[u][v]=bk[u+1][v]||bk[u][v+1];
            if(!bk[u][v])q.push(mkp(u-1,v)),q.push(mkp(u,v-1));
            else if(pth[u][v])node.eb(u,v);
        }
        paint();
        for(auto[u,v]:node){
            if(!pth[u][v+1]||bk[u][v+1])continue;
            pii t=dfs2(u+1,v);
            ed=mkp(u,v+1),dfs3(t.first-1,t.second);
        }
        paint();
    }
}p1,p2;

signed main(){
    n=read(),m=read();
    p1.n=n,p1.m=m,p2.n=m,p2.m=n;
    forto(i,1,n)forto(j,1,m)p1.a[i][j]=p2.a[j][i]=read();
    p1.init(),p2.init();
    q=read();
    queue<pii>que;
    while(q--){
        int x=read(),y=read();
        if(p1.pth[x][y]&&p2.pth[y][x])puts("0");
        else puts("1"),p1.del(x,y),p2.del(y,x);
    }
    return 0;
}