CodeForces1214D-白红宇

CodeForces1214D

阅读量：5288 次

发布时间：2019-06-14

本文共 2596 字，大约阅读时间需要 8 分钟。

这个题据我所知有两种比较优秀的做法.

第一种是\(DP\)统计每个点的路径数,然后找出必经点,再从必经点开始\(bfs\)堵路.

第二种比较简单,你先\(bfs\)一遍,如果不连通,直接输出\(0\),否则,找到任意一条路径(可以发现,一定是最短路)堵死.

然后重复这个过程,进行了几次\(bfs\)就需要至少几个障碍来堵路.

这其实有点类似于网络流最大流算法\(Dinic\)中的每次走一条阻塞流.

正确性,从终点的两个来路考虑即可.

\(Code:\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #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
                
                 #define int long long#define pb push_backusing 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 ;}