POJ 2386 Lake Counting(DFS)

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:

3

题目链接

这道题的样例很明显是三块池塘，题意是要求有几块吃糖，单独孤立的一块积水也算是一块池塘。

用DFS搜索一遍农场，遇到"W"积水将它改变为土地保证以后不会再次搜索接着搜索它的八个方向，依次递归搜索，直到搜索不到"W"积水为止，结果+1。

AC代码:

#include <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>

using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int maxn = 110;

char field[maxn][maxn];     // 农场“地形”字符数组
int N,M,res;

// 深度优先搜索
void dfs(int x,int y) {
    // 将搜索到的积水标记为土地，保证不会被再次搜索
    field[x][y] = '.';
    // 在八个方向中搜索积水
    for (int dx= -1;dx <= 1;dx++) {
        for (int dy = -1;dy <= 1;dy++) {
            // 确定搜索坐标
            int nx = x + dx;
            int ny = y + dy;
            // 如果积水在农场范围内则再次对搜索到的积水进行dfs递归搜索
            if (0 < nx && nx <= N && 0 < ny && ny <= M && field[nx][ny] == 'W') {
                dfs(nx,ny);
            }
        }
    }
}

int main() {
    // 加速输入输出
    ios::sync_with_stdio(0);
    cin.tie(0);
    // 输入农场范围
    cin >> N >> M;
    // 输入农场“地形”
    for (int i = 1;i <= N;++i) {
        for (int j = 1;j <= M;++j) {
            cin >> field[i][j];
        }
    }
    // 对每一块地进行深度优先搜索
    for (int i = 1;i <= N;++i) {
        for (int j = 1;j <= M;++j) {
            if (field[i][j] == 'W') {
                dfs(i,j);
                res++;
            }
        }
    }
    cout << res;
    return 0;
}