POJ 2386 Lake Counting DFS水水 - 细语呢喃 - 博客频道 - CSDN.NET

http://poj.org/problem?id=2386

题目大意：
有一个大小为N*M的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出院子里共有多少水洼？
思路：
水题~直接DFS，DFS过程把途中表示水洼的W改为'.'，看DFS了几次即可。

1. const int MAXN=100+10;  
2. char map[MAXN][MAXN];  
3. int n,m;  
4. void dfs(int x,int y)  
5. {  
6.     if(map[x][y]=='.')  
7.         return ;  
8.   
9.      map[x][y]='.';  
10.      dfs(x+1,y+1);  
11.      dfs(x,y+1);  
12.      dfs(x-1,y+1);  
13.      dfs(x-1,y);  
14.      dfs(x-1,y-1);  
15.      dfs(x,y-1);  
16.      dfs(x+1,y-1);  
17.      dfs(x+1,y);      
18. }  
19.   
20. int main()  
21. {  
22.     while(~scanf("%d%d",&n,&m))  
23.     {  
24.         for(int i=1;i<=n;i++)  
25.             scanf("%s",map[i]+1);  
26.   
27.         for(int i=0;i<=n+1;i++)  
28.             map[i][0]=map[i][m+1]='.';  
29.         for(int i=0;i<=m+1;i++)  
30.             map[0][i]=map[n+1][i]='.';  
31.   
32.         int ans=0;  
33.         for(int i=0;i<=n+1;i++)  
34.         {  
35.             for(int j=0;j<=m+1;j++)  
36.             {  
37.                 if(map[i][j]=='W') {  
38.                     ans++;  
39.                     dfs(i,j);  
40.                 }  
41.             }  
42.         }  
43.         printf("%d\n",ans);  
44.     }  
45.   
46.     return 0;  
47. }

Read full article from POJ 2386 Lake Counting DFS水水 - 细语呢喃 - 博客频道 - CSDN.NET