Lake Counting
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 22861Accepted: 11530
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 12W……..WW……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.
题意：.是土地W是水洼 求有多少出水洼相邻的W算是一个连通的水洼
题解：依次搜索每一个点如果是W ans++并进入dfs吧相邻的所有点变成. 最后输出ans
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 110;int N, M;char fi[maxn][maxn]; //矩形区域void dfs(int x, int y); //搜索int main(){scanf("%d%d", &N, &M);for(int i = 0; i < N; ++i){scanf("%s", fi[i]);}int ans = 0;for(int i = 0; i < N; ++i){for(int j = 0; j < M; ++j){if(fi[i][j] == 'W'){ //如果是W进入递归dfs(i, j);++ans;//水洼+1}}}printf("%d\n", ans);return 0;}void dfs(int x, int y){fi[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 && fi[nx][ny] == 'W'){ //搜索前后左右dfs(nx, ny);//如果是W进入循环}}}}
，想起那座山，那个城，那些人……
