题目链接：https://vjudge.net/problem/2728294/origin
思路：可以抽象成管道，先试试能不能找到一个通道能通到终点，
如果可以则封锁这个通道，一个石头即可，
再试试能不能找到另一个通道能到达终点，
如果可以则再用一个石头封锁这个通道。
整个题目抽象成能不能找出两个独立的通道（如果不能说明需要公用一个管道），从起点流到终点。
为了充分利用格子，最合理化找出通道，应该选择靠边的方法找格子。
#include <stdio.h> #include <iostream> using namespace std; const int N = (int)1e6+100; char mp[N]; int vis[N]; int n,m; inline bool check(int x,int y){ return x>=0&&x<n&&y>=0&&y<m; } bool dfs(int x,int y){ if( !check(x,y) || vis[x*m+y] ) return false; if( x*m+y == n*m-1 ) return true; vis[x*m+y] = 1; return dfs(x,y+1) || dfs(x+1,y); } 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; } } bool flag = 1; for(int o = 0; o <= 1; o++){ vis[0] = 0; if(!dfs(0,0)){ cout << o << endl; flag = 0; break; } } if(flag) cout << 2 << endl; return 0; }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
