Lake Counting

链接：https://www.luogu.com.cn/problem/P1596

题目描述

由于近期的降雨，雨水汇集在农民约翰的田地不同的地方。我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。每个网格中有水('W') 或是旱地('.')。一个网格与其周围的八个网格相连，而一组相连的网格视为一个水坑。约翰想弄清楚他的田地已经形成了多少水坑。给出约翰田地的示意图，确定当中有多少水坑。

输入格式

• 第1行：两个空格隔开的整数：N 和 M

• 第2行到第N+1行：每行M个字符，每个字符是'W'或'.'，它们表示网格图中的一排。字符之间没有空格。

输出格式

• 一行：水坑的数量

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.

理解：

  'W'代表着积水，而'.'代表着干的地。而如果两个积水距距离<2则视作同一片水洼，求图中水洼的总量。显而易见，需要遍历所有积水，并确定它的周围八个点是否都为干地，利用深度优先算法。

题解：

#include <iostream>
using namespace std;
#define MAX 100
int n, m;
char arr[MAX][MAX];
void dfs(int x, int y)
{
    arr[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 (nx >= 0 && ny >= 0 && nx < n && ny < m && arr[nx][ny] == 'W')
                dfs(nx, ny);
        }
    return;
}
int main()
{
    int num = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> arr[i][j];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            if (arr[i][j] == 'W')
            {
                dfs(i, j);
                num++;
            }
        }
    cout << num << endl;
    system("pause");
}