深搜 灌水

这题 我们就相当于求 路径上不经过 * 能到达边界的点有几个

然后我就可以从边界上开始灌水，染色，遇到 * 就 return

然后就相当于 没有被洪水填到的就是 不会到边界的节点

 

1 include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 #include 
            
              9 using namespace std ;10 11 const int dx[5] = { 0,1,0,0,-1},12 dy[5] = { 0,0,1,-1,0} ;13 int n,m,ans ;14 char a[501][501] ;15 16 inline bool pd(int xx,int yy) 17 {18 if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[xx][yy]=='0') return true ;19 return false ; 20 }21 22 void dfs(int x,int y ) 23 {24 int xx,yy ;25 for(int i=1;i<=4;i++) 26 {27 xx = x+dx[i] ;28 yy = y+dy[i] ;29 if(pd(xx,yy)) 30 {31 a[xx][yy] = '*' ;32 dfs(xx,yy) ;33 }34 }35 }36 37 int main() 38 {39 scanf("%d%d",&n,&m) ;40 for(int i=1;i<=n;i++) 41 scanf("%s",a[ i ]+1) ;42 for(int i=1;i<=n;i++) 43 {44 if(a[i][1]=='0') a[i][1] = '*',dfs(i,1) ; 45 if(a[i][m]=='0') a[i][m] = '*',dfs(i,m) ;46 }47 for(int i=1;i<=m;i++)48 {49 if(a[1][i]=='0') a[1][i] = '*',dfs(1,i) ;50 if(a[n][i]=='0') a[n][i] = '*',dfs(n,i) ;51 }52 ans = 0 ;53 for(int i=1;i<=n;i++) 54 for(int j=1;j<=m;j++) if(a[i][j]=='0') ans++ ;55 printf("%d\n",ans) ; 56 return 0 ;57 }