洼地编程初二练习问题

Question

题目描述
由于近期的降雨，小刚的田地里产生了许多的洼地。我们用一个NxM(1<=N<=100;1<=M<=100)网格图表示。每个网格中有水('W'，大写W) 或是旱地('.')。一个网格与其周围的八个网格相连，而一组可以相互连通的'W'网格视为一个洼地。小刚想弄清楚他的田地已经形成了多少个洼地。给出田地的示意图，确定当中有多少个洼地。

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

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

输出格式
一个整数，表示洼地的数量

说明/提示
一共有3个洼地，左上一个，左下一个，右边一个。

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

#include <iostream>
#include <vector>
using namespace std;

void dfs(int x, int y, vector<vector<char>>& grid) {
    if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '.') {
        return;
    }
    grid[x][y] = '.';
    dfs(x - 1, y, grid);
    dfs(x + 1, y, grid);
    dfs(x, y - 1, grid);
    dfs(x, y + 1, grid);
    dfs(x - 1, y - 1, grid);
    dfs(x - 1, y + 1, grid);
    dfs(x + 1, y - 1, grid);
    dfs(x + 1, y + 1, grid);
}

int countBasins(vector<vector<char>>& grid) {
    int count = 0;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == 'W') {
                dfs(i, j, grid);
                count++;
            }
        }
    }
    return count;
}

int main() {
    int N, M;
    cin >> N >> M;
    vector<vector<char>> grid(N, vector<char>(M));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cin >> grid[i][j];
        }
    }
    cout << countBasins(grid) << endl;
    return 0;
}