题意:给你一张图 ,从 1,1走到 n , m 问最少堵多少点,使得路不连通
解: 最多 2 个, 两次深搜。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int dir[2][2] = {1,0,0,1};
int s,t;
char mp[maxn];
int n,m,vis[maxn];
int ans;
void dfs(int id){
if(ans)return ;
if(id==t){
ans++;return;
}
int y = id%m, x = id/m;
for(int i=0;i<=1;i++){
int tx = x+dir[i][0];
int ty = y+dir[i][1];
if(tx>=n||ty>=m||vis[tx*m+ty])continue;
vis[tx*m+ty] = 1;
dfs(tx*m+ty);
if(ans)return;
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++){
scanf("%s",mp+i*m);
for(int j=i*m;j<(i+1)*m;j++){
if(mp[j]=='#')vis[j] = 1;
}
}
s = 0,t = n*m-1;
vis[s] = 1; vis[t] = 0;
dfs(s);
if(!ans){
printf("0\n");
return 0;
}
vis[s] = 1; vis[t] = 0;
ans = 0;
dfs(s);
if(ans){
printf("2\n");
}else printf("1\n");
return 0;
}