Link
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;
}