算法题：水坑问题

问题描述

Due to recent rains, water has pooled in various places in Farmer John's field, which is represented by a rectangle of N×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.

输入格式

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.

输出格式

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

样例1

输入

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

输出

3

样例2

输入

5 6
W...W.
W.W..W
...W.W
W.WW..
....WW

输出

4

解决方案

思路

广度优先搜索

代码

#include <iostream>
#include <queue>

using namespace std;

int n, m;
char arr[105][105];

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    while (!q.empty()) {
        pair<int, int> point = q.front();
        q.pop();

        int offset_x[] = {1, -1, 0, 0, -1, 1, 1, -1};
        int offset_y[] = {0, 0, 1, -1, -1, 1, -1, 1};
        for (int i = 0; i < 8; ++i) {
            int xx = point.first + offset_x[i];
            int yy = point.second + offset_y[i];
            if (xx >= 0 && xx < n && yy >= 0 && yy < m && arr[xx][yy] == 'W') {
                arr[xx][yy] = '0';
                q.push({xx, yy});
            }
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> arr[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (arr[i][j] == 'W') {
                ans++;
                bfs(i, j);
            }
        }
    }

    cout << ans;

    return 0;
}