洛谷P2327 [SCOI2005]扫雷

枚举 搜索

对搜索的 一些优化

其实我们只要枚举第一行是否有地雷，根据第1行探测出的地雷数，就可以推出第二行是否有地雷

然后在根据第二行探测地雷数推出第三行的情况，这样以此类推，一直推到第 n-1 的探测结果，

然后 推出第 n 行是否有地雷

如果在推的过程中 使得当前的探测地雷数为 负数 ，说明这个方法是萎的，

或者这一行推完了之后，还是有雷，那也退出，最后还要判断一下第 n 行是否有地雷

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 using namespace std ; 10 11 const int maxn = 100011 ; 12 int n,ans ; 13 int a[maxn],b[maxn] ;14 bool f[maxn] ;15 bool flag,ok ; 16 17 int main() 18 {19 scanf("%d",&n) ; 20 for(int i=1;i<=n;i++) 21 scanf("%d",&a[ i ]),b[ i ] = a[ i ] ; 22 flag = false ; 23 for(int i=0;i<=1;i++) 24 {25 for(int j=1;j<=n;j++) f[ j ] = 0,a[ j ] = b[ j ] ; 26 f[ 1 ] = i ; 27 if(f[1]) a[ 1 ]--,a[ 2 ]-- ;28 ok = false ; 29 for(int j=1;j<=n-1;j++) 30 {31 if( a[ j ]<0 ) 32 {33 ok = true ; 34 break ; 35 }36 if(a[ j ]>0) f[ j+1 ] = 1,a[ j ]--,a[j+1]--,a[j+2]-- ; 37 if(a[ j ]) 38 {39 ok = true ; 40 break ; 41 } 42 }43 if(ok) continue ; 44 if(a[n]) continue ; 45 ans++ ; 46 }47 printf("%d\n",ans) ; 48 return 0 ; 49 }