POJ 2386 Lake Counting DFS

2018-06-27 09:42:41来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题目链接:http://poj.org/problem?id=2386

思路很简单,就是一个标准的DFS,不断从W开始遍历,每遍历一个W就改成".",然后朝八个方向深搜,要注意边界。如果八个方向都搜完了,一次深搜就结束了。

那么进行几次深搜就意味着有几个连通的区域。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 105;
 4 int N,M;
 5 char field[maxn][maxn];
 6 
 7 void dfs(int x,int y){
 8     field[x][y] = '.';
 9     
10     for(int i=-1;i<=1;++i){
11         for(int j=-1;j<=1;++j){
12             int a = x+i, b = y+j;
13             if(a>=0 && a<N && b>=0 && b<M && field[a][b] == 'W')
14                 dfs(a,b); 
15         }
16     }
17     return ;
18 } 
19 
20 int main(){
21     cin>>N>>M;
22     for(int i=0;i<N;++i){
23         for(int j=0;j<M;j++)
24             cin>>field[i][j];
25     }
26     int ans = 0;
27     for(int i=0;i<N;++i){
28         for(int j=0;j<M;++j){
29             if(field[i][j] == 'W'){
30                 dfs(i,j);
31                 ans++; 
32             }
33         }
34     }
35     cout<<ans;
36     return 0;
37 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:BZOJ1569: [JSOI2008]Blue Mary的职员分配(dp 暴力)

下一篇:BZOj1261: [SCOI2006]zh_tree(dp)