题解：P11454 [USACO24DEC] 2D Conveyer Belt S

· · 题解

这是我的一个悲惨的做题故事，在考试时没发现问题就错了两个测试点 T_T。 算法： 两次 dfs！

解法： 我们先 dfs 一次把最后的结果给算好。再一个一个移除点，然后把每一个移除的点标记为任意传送带，如果移除后的点从不行 ( 0 ) 到了行 ( 1 )，检查附近指向这个点的传送带。然后记录被改变点的数量，以此类推。

拿第一个样例。 输入完后的结果因该是：

R L ?
U ? ?
? D L
不知道怎么消除那个加粗表格。现在我们的结果是 3 个不可行，然后删除最后一个输入 (2 1 U)，改成?。 R L ?
? ? ?
? D L
发现这个点从不行到可行了，把结果减一。再 dfs 上下左右不可行且指这个点的点。操作完后的结果为 2。再删除倒数第二个输入 (1 2 L) R ? ?
? ? ?
? D L

现在发现当前节点从不可行变可行了，把结果减一。dfs 上下左右，发现 (1，1) 也变了，再把结果减一。操作完后的结果为 0。当结果为 0 时，后面就不用搜了，因为删掉元素后不会增多可行的数量。

real_ans 的最终结果 (从 0 到 cnt ) 是 {3, 2, 0, 0, 0, 0, 0}，所以输出时加个 cnt--

Talk is cheap, here is my code：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool vis[5002][5002],f[5002][5002];
char lst[5002][5002], direction;
struct node{
    int x,y;
}backward[200002];

ll n,Q,a,b,real_ans[200002],cnt,ans;
void dfs(int x,int y) {
    f[x][y]=1;
    if(x==0||y==0||x==n+1||y==n+1)return;
    if(vis[x][y]) return;
    else vis[x][y]=1;
    if(lst[x][y+1]=='L'||lst[x][y+1]=='?') dfs(x,y+1);
    if(lst[x][y-1]=='R'||lst[x][y-1]=='?') dfs(x,y-1);
    if(lst[x-1][y]=='D'||lst[x-1][y]=='?') dfs(x-1,y);
    if(lst[x+1][y]=='U'||lst[x+1][y]=='?') dfs(x+1,y);

}
void dfs2(int x,int y){
    if (x==0||y==0||x==n+1||y==n+1) {
        f[x][y]=1;
        return;
    }
    if(y<n&&((lst[x][y+1]=='L'||lst[x][y+1]=='?')&&f[x][y+1]==0)){
        f[x][y+1]=1;
        ans--;
        dfs2(x,y+1);
    }
    if(y>1&&((lst[x][y-1]=='R'||lst[x][y-1]=='?')&&f[x][y-1]==0)){
        f[x][y-1]=1;
        ans--;
        dfs2(x,y-1);
    }
    if(x>1&&((lst[x-1][y]=='D'||lst[x-1][y]=='?')&&f[x-1][y]==0)){
        f[x-1][y]=1;
        ans--;
        dfs2(x-1,y);
    }
    if(x<n&&((lst[x+1][y]=='U'||lst[x+1][y]=='?')&&f[x+1][y]==0)){
        f[x+1][y]=1;
        ans--;
        dfs2(x+1,y);
    }
}

int main(){
//    freopen("cin.in","r",stdin);
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); // 加输入/输出的速度
    //输入+初始化
    cin>>n>>Q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            lst[i][j]='?';

    memset(vis,0,sizeof(vis));
    memset(f,0,sizeof(f));
    for (int i=Q;i>=1;i--) {
        cin>>a>>b>>direction;
        backward[i].x=a;
        backward[i].y=b;
        lst[a][b]=direction;
    }
    for (int i=1;i<=n;i++){ // 把边界都设为可行
        f[0][i]=1;
        f[n+1][i]=1;
        f[i][0]=1;
        f[n+1][i]=1;
    }

    // 一次dfs算完全部
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(!vis[i][j]){
                if(j==1&&(lst[i][j]=='?'||lst[i][j]=='L')) dfs(i,j);
                if(j==n&&(lst[i][j]=='?'||lst[i][j]=='R')) dfs(i,j);
                if(i==n&&(lst[i][j]=='?'||lst[i][j]=='D')) dfs(i,j);
                if(i==1&&(lst[i][j]=='?'||lst[i][j]=='U')) dfs(i,j);
            }

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) if(!f[i][j]) ans++;

    // 核心代码!!! 反过来算
    real_ans[cnt++]=ans;
    for (int i=1;i<=Q;i++){
        if (cnt==0){
            real_ans[cnt++]=0;
            continue;
        }
        int tmp1=backward[i].x,tmp2=backward[i].y;
        lst[tmp1][tmp2]='?';
        if (f[tmp1][tmp2]==0){
            if     (f[tmp1][tmp2+1]==1) f[tmp1][tmp2]=1;
            else if(f[tmp1][tmp2-1]==1) f[tmp1][tmp2]=1;
            else if(f[tmp1-1][tmp2]==1) f[tmp1][tmp2]=1;
            else if(f[tmp1+1][tmp2]==1) f[tmp1][tmp2]=1;
            else if(tmp1==0||tmp2==0||tmp1==n||tmp2==n) f[tmp1][tmp2]=1;
            if (f[tmp1][tmp2]==1) {
                ans--;
                dfs2(tmp1,tmp2);
            }
        }
        real_ans[cnt++]=ans;
    }

    // 我们多加了一次，把这个减回去
    cnt--;
    while (cnt--) cout<<real_ans[cnt]<<endl;
    return 0;
}