題目鏈接：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; }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/136663.html
標籤：其他