当前位置：首页 > article >正文

P1596 [USACO10OCT] Lake Counting S（深度优先搜索）

article 2025/3/3 12:41:03

题目描述

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.

输入格式

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.

题意翻译

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

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

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

输出一行，表示水坑的数量。

输入输出样例

输入

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

输出

说明/提示

OUTPUT DETAILS: There are three ponds: one in the upper left, one in the lower left, and one along the right side.

#include <bits/stdc++.h>
using namespace std;

// 全局变量定义
int row, col;                     // 地图的行数和列数
vector<vector<char>> b;           // 存储地图数据，'W'表示水，'.'表示旱地
vector<vector<bool>> v;           // 标记数组，记录每个位置是否被访问过
int dx[] = {1, -1, 0, 0, 1, -1, -1, 1}; // 8个方向的x偏移量（上下左右+4个对角线）
int dy[] = {0, 0, 1, -1, 1, 1, -1, -1}; // 8个方向的y偏移量
int res = 0;                      // 统计水坑的数量

// 深度优先搜索函数：标记并淹没当前水坑区域
void dfs(int x, int y) {
    v[x][y] = true;              // 标记当前位置为已访问
    b[x][y] = '.';               // 将水坑淹没，避免后续重复统计
    
    // 遍历8个相邻方向
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];      // 计算新位置的x坐标
        int ny = y + dy[i];      // 计算新位置的y坐标
        
        // 检查新位置是否合法、未被访问且是水坑
        if (nx >= 1 && nx <= row && ny >= 1 && ny <= col 
            && !v[nx][ny] && b[nx][ny] == 'W') {
            dfs(nx, ny);        // 递归处理相邻水坑区域
        }
    }
}

int main() {
    // 输入行数和列数
    cin >> row >> col;
    
    // 初始化地图和访问标记数组（从1开始索引）
    b.resize(row + 1, vector<char>(col + 1));
    v.resize(row + 1, vector<bool>(col + 1, false));
    
    // 读入地图数据
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            cin >> b[i][j];
        }
    }
    
    // 遍历地图的每个位置
    for (int i = 1; i <= row; i++) {
        for (int j = 1; j <= col; j++) {
            // 发现未被访问的水坑起点
            if (b[i][j] == 'W' && !v[i][j]) {
                dfs(i, j);      // 淹没并标记整个水坑区域
                res++;           // 水坑数量增加
            }
        }
    }
    
    // 输出最终的水坑数量
    cout << res << endl;
    
    return 0;
}

代码思路详解

变量与初始化
- row 和 col 存储地图的行列数。
- b 是二维字符数组，存储原始地图（W 表示水坑，. 表示旱地）。
- v 是二维布尔数组，标记每个位置是否被访问过。
- dx 和 dy 定义了8个方向（上下左右+对角线），用于搜索相邻水坑。
DFS核心逻辑
- 标记与淹没：当进入DFS时，立即将当前位置标记为已访问（v[x][y] = true），并将地图中的 W 改为 .（淹没该位置，避免主循环重复统计）。
- 递归搜索相邻区域：遍历8个方向，对每个合法且未被访问的水坑位置（W）递归调用DFS，确保整个连通区域被处理。
主循环遍历
- 寻找水坑起点：主函数遍历地图的每个位置，当遇到未被访问的 W 时，触发一次DFS。
- 统计水坑数量：每次DFS结束后，水坑数量 res 自增1，表示发现一个独立水坑。
关键设计点
- 双重标记：通过 v 数组防止DFS内部重复访问，通过修改 b 数组防止主循环重复统计。
- 8方向处理：通过 dx 和 dy 数组实现对角线和四邻域的快速遍历。
- 注意这里的标记访问是放在函数一进来的时候，因为初始位置不包括在8个方向的数组里面的