CodeForces1214D-蒲公英云

CodeForces1214D

CodeForces1214D
这个题据我所知有两种比较优秀的做法.
第一种是\(DP\)统计每个点的路径数,然后找出必经点,再从必经点开始\(bfs\)堵路.
第二种比较简单,你先\(bfs\)一遍,如果不连通,直接输出\(0\),否则,找到任意一条路径(可以发现,一定是最短路)堵死.
然后重复这个过程,进行了几次\(bfs\)就需要至少几个障碍来堵路.
这其实有点类似于网络流最大流算法\(Dinic\)中的每次走一条阻塞流.
正确性,从终点的两个来路考虑即可.
\(Code:\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <ctime> #include <map> #include <set> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> #define int long long #define pb push_back using std::set ; using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; using std::swap ; using std::sort ; using std::unique ; using std::greater ; template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ; } template < class T > inline void write (T x) { static T stk[100] , top = 0 ; if ( x == 0 ) { putchar ('0') ; return ; } if ( x < 0 ) { x = - x ; putchar ( '-' ) ; } while ( x ) { stk[++top] = x % 10 ; x /= 10 ; } while ( top ) { putchar ( stk[top--] + '0' ) ; } putchar ('\n') ; } const int N = 1e6 + 100 ; std::queue < pii > q ; char e[N] ; int n , m , pre[N] ; bool fbd[N] , mk[N] ; int fx[] = { 0 , 1 } ; int fy[] = { 1 , 0 } ; inline void bfs () { q.push ( { 1 , 1 } ) ; mk[1] = true ; while ( ! q.empty () ) { int dx = q.front ().X , dy = q.front().Y ; q.pop () ; rep ( i , 0 , 1 ) { int tx = dx + fx[i] , ty = dy + fy[i] ; int cur = m * ( tx - 1 ) + ty ; if ( tx < 1 || ty < 1 || tx > n || ty > m || fbd[cur] || mk[cur] || e[cur] == '#' ) continue ; mk[cur] = true ; pre[cur] = m * ( dx - 1 ) + dy ; q.push ( { tx , ty } ) ; } } return ; } signed main (int argc , char * argv[] ) { n = rint () ; m = rint () ; rep ( i , 1 , n ) scanf ("%s" , e + m * ( i - 1 ) + 1 ) ; bfs () ; if ( ! mk[m*(n-1)+m] ) { puts ("0") ; return 0 ; } MEM ( mk , 0 ) ; for (int i = m*(n-1)+m ; i ; i = pre[i] ) if ( i != 1 && i != m*(n-1)+m ) fbd[i] = true ; bfs () ; if ( ! mk[m*(n-1)+m] ) { puts ("1") ; return 0 ; } MEM ( mk , 0 ) ; for (int i = m*(n-1)+m ; i ; i = pre[i] ) if ( i != 1 && i != m*(n-1)+m ) fbd[i] = true ; bfs () ; if ( ! mk[m*(n-1)+m] ) { puts ("2") ; return 0 ; } return 0 ; }