题解

#include <bits/stdc++.h>
using namespace std;
int n, m, sum;
char mp[105][105];
bool vis[105][105];
int dx[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
int dy[8] = {0, 0, -1, 1, -1, -1, 1, 1};
void dfs(int x, int y) {
    mp[x][y] = '.';
    for (int i = 0;i < 8;i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && mp[nx][ny] == 'W') {
            dfs(nx, ny);
        }
    }
}
int main () {
    cin >> n >> m;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> mp[i][j];
        }
    }
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (mp[i][j] == 'W') {
                dfs(i, j);
                sum++;
            }
        }
    }
    cout << sum;
    return 0;
}

代码结构解析

1. 头文件与命名空间

#include <bits/stdc++.h>  // 包含所有标准库，简化代码
using namespace std;     // 使用标准命名空间，避免重复写std::

2. 全局变量定义

int n, m, sum;           // n：行数；m：列数；sum：水坑数量（结果）
char mp[105][105];       // 存储网格图（105是预留空间，避免越界）
int dx[8] = {-1, 1, 0, 0, -1, 1, -1, 1};  // 8个方向的x偏移量
int dy[8] = {0, 0, -1, 1, -1, -1, 1, 1};  // 8个方向的y偏移量

• dx和dy数组用于表示从当前位置出发，8 个相邻方向的坐标变化（例如：dx[0]=-1, dy[0]=0表示正上方）。

3. DFS 函数（深度优先搜索）

void dfs(int x, int y) {
    mp[x][y] = '.';  // 将当前'W'标记为旱地，避免重复访问
    // 遍历8个方向
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];  // 新x坐标
        int ny = y + dy[i];  // 新y坐标
        // 检查新坐标是否合法（在网格内且是'W'）
        if (nx >= 1 && ny >= 1 && nx <= n && ny <= m && mp[nx][ny] == 'W') {
            dfs(nx, ny);  // 递归访问相邻的'W'
        }
    }
}

• 作用：从一个 'W' 出发，递归遍历所有与其相连的 'W'，并将它们标记为旱地（'.'），从而将一整个相连的水坑 "消除"。

4. 主函数

int main() {
    cin >> n >> m;  // 输入网格大小
    // 读取网格数据（注意：这里用1-based索引，即行和列从1开始）
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> mp[i][j];
        }
    }
    // 遍历整个网格，寻找未被处理的'W'
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (mp[i][j] == 'W') {
                dfs(i, j);  // 处理一个新的水坑
                sum++;      // 水坑数量加1
            }
        }
    }
    cout << sum;  // 输出结果
    return 0;
}

算法逻辑

1.读取输入：先获取网格的行数n和列数m，再读取整个网格。

2.遍历网格：逐个检查每个单元格，若发现一个未被处理的 'W'（即一个新水坑的起点）：

• 调用dfs函数，将该 'W' 及其所有相连的 'W' 都标记为旱地（避免重复计数）。
• 每处理完一个相连的 'W' 区域，就将水坑数量sum加 1。

3.输出结果：最终sum即为水坑的总数量。

示例说明

对于输入样例中的 $10×12$ 网格，代码会：

找到第一个 'W'，通过 DFS 将其相连的所有 'W' 标记为 '.'，计数 1。

• 继续遍历，找到下一个未被标记的 'W'，重复上述过程，计数 2。

• 最后找到第三个独立的 'W' 区域，计数 3。

• 最终输出 3，与样例结果一致。

该算法通过 DFS 实现了对连通区域的遍历，时间复杂度为 $O (N×M)$（每个单元格最多被访问一次），适合题目中 $N$ 和 $M$ 不超过 100 的规模。

链接描述1
链接描述2