DFS:深入优先搜索 POJ-2386 Lake Counting

 深度优先搜索是从最开始的状态出发，遍历所有可以到达的状态。

因此可以对所有的状态进行操作，或列举出所有的状态。

---

Lake Counting

 POJ - 2386 

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

3

Hint

OUTPUT DETAILS:  There are three ponds: one in the upper left, one in the lower left,and one along the right side.

---

#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<queue> #include<map> #include<set> #include<algorithm> #include<cmath> #include<cstdlib> using namespace std; int m, n; char garden[105][105]; void dfs(int x, int y) { //将当前点取消标记，避免重复查找 garden[x][y] = '.'; //遍历周围的八个点 for (int dx = -1; dx <= 1; dx++){ for (int dy = -1; dy <= 1;dy++){ int nx = x + dx; int ny = y + dy; if(0<=nx && nx<n && 0<=ny && ny<m && garden[nx][ny]=='W') dfs(nx, ny); } } } int main(void) { while(~scanf("%d%d", &n,&m)){ getchar(); //吸收两数字后的换行符 memset(garden, 0, sizeof(garden)); for (int i = 0; i < n;i++){ for (int j = 0; j < m;j++) scanf("%c", &garden[i][j]); getchar(); //吸收每次输入一行后的换行符 } int sum = 0; for (int i = 0; i < n; i++){ for (int j = 0; j < m; j++){ if (garden[i][j] == 'W'){ dfs(i, j); sum++; } } } cout << sum << endl; } return 0; }