Link

华中师范大学2023新生赛 D 身无彩凤双飞翼

Question

给出一个 \(n\times m\) 的网格，网格上有一些障碍，问最少添加多少障碍才能使 \((1,1)\) 和 \((n,m)\) 不连通

Solution

我好像用了一种和标答不一样的写法

我们先对图 bfs 一次，如果 \((1,1)\) 不能到达 \((n,m)\) ，则图本来就不连通，需要添加 \(0\) 个障碍

然后把一条 \((1,1)\) 到 \((n,m)\) 的路径堵上，再次 bfs，如果还是连通，则答案就是 \(2\)，否则答案就是 \(1\)

答案不可能大于 \(2\)，把 \((1,2)\) 和 \((2,1)\) 堵上就不可能连通了

标答是这么写的

设 \(f[i][j]\) 表示从 \((1,1)\) 走到 \((i,j)\) 的方案数，\(g[i][j]\) 表示从 \((n,m)\) 走到 \((i,j)\) 的方案数。

如果左上角走不到右下角，则答案为 \(0\)

如果存在某个位置，满足 \(f[i][j]\times g[i][j]\) 等于总方案数，则答案为 \(1\)。

否则答案为 \(2\)

考虑到方案数比较多，判断答案为 \(1\) 时需要用到哈希

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;

int n,m,k;
int b[maxn][maxn];
int vis[maxn][maxn];
struct node{int x,y;}pre[maxn][maxn];

int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
    return ret*f;
}

bool bfs(){
    queue<node> q;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        vis[i][j]=(b[i][j]);
    q.push((node){1,1});vis[1][1]=0;
    while(!q.empty()){
        int x=q.front().x,y=q.front().y;q.pop();int x_,y_;

        if(x==n&&y==m) {
            while(1) {
                node pre_node=pre[x][y];
                if(pre_node.x==1&&pre_node.y==1) return 1;
                else x=pre_node.x,y=pre_node.y;
                b[x][y]=1;
            }
        }

        x_,y_;x_=x+1,y_=y;
        if(x_<=n&&y_<=m&&vis[x_][y_]==0){
            q.push((node){x_,y_});
            vis[x_][y_]=1;pre[x_][y_]=(node){x,y};
        }

        x_,y_;x_=x,y_=y+1;
        if(x_<=n&&y_<=m&&vis[x_][y_]==0){
            q.push((node){x_,y_});
            vis[x_][y_]=1;pre[x_][y_]=(node){x,y};
        }
    }
    return 0;
}

int main(){
    freopen("D.in","r",stdin);
    n=read(),m=read(),k=read();
    for(int i=1;i<=k;i++){
        int x=read(),y=read();
        b[x][y]=1;
    }
    if(!bfs()) printf("0\n");
    else if(!bfs()) printf("1\n");
    else printf("2\n");
    return 0;
}