P1596 Lake Counting S

calendar May 8, 2026 · 5 分钟阅读 · 深度优先搜索  ·
分享到: linkedin copy

文章目录

题目信息

字段 内容
题号 P1596
难度 普及-
知识点 搜索、DFS、Flood Fill

题目描述

由于近期降雨，雨水汇集在农民约翰的田地不同地方。

用一个 N × M 的网格图表示田地，每个格子中为水 'W' 或旱地 '.'。

一个格子与其周围的八个方向（上、下、左、右及四个对角）相邻的格子相连。一组相连的水格子视为一个水坑（pond）。

请你统计田地中共有多少个水坑。

输入格式

  • 第一行：两个整数 N M（行数和列数）
  • 接下来 N 行：每行 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.

输出

3

数据范围

  • 1 ≤ N ≤ 100
  • 1 ≤ M ≤ 100

解题思路

核心思想

本题是 Flood Fill（洪水填充） 的典型应用，本质是求八连通的连通块数量。

思路非常简单：

  1. 遍历整个网格图的每个格子
  2. 若遇到未访问的水 'W'，则启动一次 DFS，将其所在的整个连通块全部标记为已访问（改为 '.''），水坑计数器 +1
  3. 重复直到遍历结束，计数器即为水坑数量

DFS 填充过程

DFS(x, y):
    将 a[x][y] 标记为已访问（改为 '.'）
    遍历八个方向 (dx, dy):
        若相邻格子在范围内且为 'W':
            DFS(相邻格子)

边界检查

在 DFS 中检查 (dx, dy) 是否在 [0, n) × [0, m) 范围内（注意：行上限是 < n，不是 <= n）。

完整代码

C++

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

int n, m;
char a[101][101];
int ans;

void dfs(int x, int y) {
    a[x][y] = '.';
    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            if (dx == 0 && dy == 0) continue;
            int nx = x + dx;
            int ny = y + dy;
            // 修复：行上限用 < n 而非 <= n
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] == 'W') {
                dfs(nx, ny);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

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

    cout << ans << '\n';
    return 0;
}

关键代码讲解

八方向枚举

for (int dx = -1; dx <= 1; dx++) {
    for (int dy = -1; dy <= 1; dy++) {
        if (dx == 0 && dy == 0) continue;   // 跳过中心格子

dx ∈ {-1, 0, 1}，dy ∈ {-1, 0, 1}，共 9 种组合；排除中心 (0,0) 后恰好是八个方向。也可以预先定义方向数组简化：

int dir[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
for (int k = 0; k < 8; k++) {
    int nx = x + dir[k][0];
    int ny = y + dir[k][1];
    ...
}

就地标记（无需 visited 数组）

a[x][y] = '.';

将访问过的 'W' 直接改写为 '.'，下次遍历时自动跳过，实现了 O(1) 的访问标记，无需额外 vis 数组。

边界检查

if (nx >= 0 && nx < n && ny >= 0 && ny < m && a[nx][ny] == 'W')
  • 行号 nx 必须满足 0 ≤ nx < n（不是 <= n）
  • 列号 ny 必须满足 0 ≤ ny < m

复杂度分析

方法 时间复杂度 空间复杂度
DFS 洪水填充 O(N × M) O(N × M)（递归栈，最坏 O(N×M)）

每个格子最多被访问一次，每个格子最多进入一次递归。

易错点

  1. 边界检查：行上限是 < n 而非 <= n
  2. 跳过自身：八方向循环中必须 if (dx==0 && dy==0) continue;，否则陷入死递归
  3. 八连通 vs 四连通：本题要求八连通（包括对角），不能只检查上下左右四个方向

其他语言解法

Python

def solve() -> None:
    import sys
    sys.setrecursionlimit(100000)
    data = sys.stdin.read().splitlines()
    n, m = map(int, data[0].split())
    # 过滤空行，防止尾部多余换行导致空行
    g = [list(line) for line in data[1:1 + n]]

    def dfs(x: int, y: int) -> None:
        g[x][y] = '.'
        for dx in (-1, 0, 1):
            for dy in (-1, 0, 1):
                if dx == 0 and dy == 0:
                    continue
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < m and g[nx][ny] == 'W':
                    dfs(nx, ny)

    ans = 0
    for i in range(n):
        for j in range(m):
            if g[i][j] == 'W':
                dfs(i, j)
                ans += 1

    print(ans)


if __name__ == '__main__':
    solve()

Java

import java.io.*;

public class Main {
    static int n, m;
    static char[][] g;
    static int[] dx = {-1, -1, -1, 0, 0, 1, 1, 1};
    static int[] dy = {-1, 0, 1, -1, 1, -1, 0, 1};

    static void dfs(int x, int y) {
        g[x][y] = '.';   // 就地标记
        for (int dir = 0; dir < 8; dir++) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 'W') {
                dfs(nx, ny);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nm = br.readLine().trim().split("\\s+");
        n = Integer.parseInt(nm[0]);
        m = Integer.parseInt(nm[1]);

        g = new char[n][m];
        for (int i = 0; i < n; i++) {
            g[i] = br.readLine().trim().toCharArray();
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j] == 'W') {
                    dfs(i, j);
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

Go

package main

import (
    "bufio"
    "fmt"
    "os"
)

var n, m int
var g [][]byte

var dir = [][2]int{
    {-1, -1}, {-1, 0}, {-1, 1},
    {0, -1},            {0, 1},
    {1, -1},  {1, 0},  {1, 1},
}

func dfs(x, y int) {
    g[x][y] = '.'
    for _, d := range dir {
        nx, ny := x+d[0], y+d[1]
        if nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 'W' {
            dfs(nx, ny)
        }
    }
}

func main() {
    in := bufio.NewReader(os.Stdin)
    fmt.Fscan(in, &n, &m)

    g = make([][]byte, n)
    for i := 0; i < n; i++ {
        fmt.Fscan(in, &g[i])
    }

    ans := 0
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            if g[i][j] == 'W' {
                dfs(i, j)
                ans++
            }
        }
    }
    fmt.Println(ans)
}

JavaScript

'use strict';

function solve() {
    const input = require('fs').readFileSync('/dev/stdin', 'utf8');
    const lines = input.split('\n').filter(line => line.length > 0);
    const [n, m] = lines[0].split(' ').map(Number);
    const g = lines.slice(1, 1 + n).map(line => line.split(''));

    const dirs = [
        [-1, -1], [-1, 0], [-1, 1],
        [0, -1],           [0, 1],
        [1, -1],  [1, 0],  [1, 1],
    ];

    // 显式栈模拟 DFS，避免递归深度溢出
    function floodFill(sx, sy) {
        const stack = [[sx, sy]];
        while (stack.length > 0) {
            const [x, y] = stack.pop();
            if (g[x][y] !== 'W') continue;
            g[x][y] = '.';
            for (const [dx, dy] of dirs) {
                const nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] === 'W') {
                    stack.push([nx, ny]);
                }
            }
        }
    }

    let ans = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (g[i][j] === 'W') {
                floodFill(i, j);
                ans++;
            }
        }
    }
    console.log(ans);
}

solve();