POJ 2386 Lake Counting

Lake Counting

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 16042		Accepted: 8118

Description

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water ('W') or dry land ('.'). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.
Given a diagram of Farmer John's field, determine how many ponds he has.

Input

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: M characters per line representing one row of Farmer John's field. Each character is either 'W' or '.'. The characters do not have spaces between them.

Output

* Line 1: The number of ponds in Farmer John's field.

Sample Input

10 12
W........WW.
.WWW.....WWW
....WW...WW.
.........WW.
.........W..
..W......W..
.W.W.....WW.
W.W.W.....W.
.W.W......W.
..W.......W.

Sample Output

DFS基础题

将已经搜过的由'W'变成'.'，统计在这张图上一共进行过多少次DFS即为答案

因为忘了删freopen，还WA一次...

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 
 6 int n,m;
 7 char garden[102][102];
 8 
 9 void dfs(int x,int y)
10 {
11     garden[x][y]='.';
12     if(garden[x-1][y-1]=='W')
13         dfs(x-1,y-1);
14     if(garden[x-1][y]=='W')
15         dfs(x-1,y);
16     if(garden[x-1][y+1]=='W')
17         dfs(x-1,y+1);
18     if(garden[x][y-1]=='W')
19         dfs(x,y-1);
20     if(garden[x][y+1]=='W')
21         dfs(x,y+1);
22     if(garden[x+1][y-1]=='W')
23         dfs(x+1,y-1);
24     if(garden[x+1][y]=='W')
25         dfs(x+1,y);
26     if(garden[x+1][y+1]=='W')
27         dfs(x+1,y+1);
28 }
29 
30 int main()
31 {
32     while(scanf("%d %d",&n,&m)==2)
33     {
34         int ans=0;
35 
36         getchar();
37 
38         for(int i=1;i<=n;i++)
39             gets(&garden[i][1]);
40         for(int j=0;j<=m+1;j++)
41             garden[0][j]=garden[n+1][j]='.';
42         for(int i=1;i<=n+1;i++)
43             garden[i][0]=garden[i][m+1]='.';
44 
45         for(int i=1;i<=n;i++)
46             for(int j=1;j<=m;j++)
47                 if(garden[i][j]=='W')
48                 {
49                     ans++;
50                     dfs(i,j);
51                 }
52 
53         printf("%d
",ans);
54     }
55     return 0;
56 }

[C++]