[USACO10OCT] Lake Counting S

GitHub跳转原题关系图返回列表

扫描网格，每遇到未访问水格就用八方向 BFS 淹掉整个连通块并把答案加一。

OJ: luogu

题目 ID: P1596

难度:普及-

标签:BFSflood fill网格python

日期: 2026-07-16 18:01

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

字符网格中，八方向相邻的所有 W 属于同一个水塘，统计水塘数量。

思路

从上到下扫描网格。每遇到一个仍为 W 的格子，它一定属于一个尚未统计的新连通块，于是答案加一，并从这里 BFS 找到整块水域。

访问水格时直接把它改成 .。这同时完成了访问标记，后续扫描和 BFS 都不会再次处理它。

Python 知识

  • 字符串不可修改，因此读取成 list(input()) 的字符列表。
  • 八个方向用列表推导式生成。
  • deque 提供 O(1)O(1) 的 popleft。
  • 直接修改网格代替额外 visited 矩阵，减少一份状态。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：deque 队列。
  • /home/rainboy/mycode/hugo-blog/content/program_language/python/bfs_shortest.md：网格邻居与 BFS 骨架。

代码

python
from collections import deque


n, m = map(int, input().split())
field = [list(input().strip()) for _ in range(n)]
directions = [
    (dx, dy)
    for dx in (-1, 0, 1)
    for dy in (-1, 0, 1)
    if (dx, dy) != (0, 0)
]
ponds = 0

for start_x in range(n):
    for start_y in range(m):
        if field[start_x][start_y] != "W":
            continue
        ponds += 1
        field[start_x][start_y] = "."
        queue = deque([(start_x, start_y)])
        while queue:
            x, y = queue.popleft()
            for dx, dy in directions:
                nxt_x, nxt_y = x + dx, y + dy
                if 0 <= nxt_x < n and 0 <= nxt_y < m and field[nxt_x][nxt_y] == "W":
                    field[nxt_x][nxt_y] = "."
                    queue.append((nxt_x, nxt_y))

print(ponds)
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P1596 [USACO10OCT] Lake Counting S */
/* 扫描网格，每遇到未访问水格就用八方向 DFS 淹掉整个连通块。 */

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

const int MAXN = 105;

int n, m;
char g[MAXN][MAXN]; // 网格
int dx[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };

// DFS 标记一个连通块
void dfs(int x, int y) {
    g[x][y] = '.'; // 标记已访问
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == 'W') {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> (g[i] + 1);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j] == 'W') {
                ans++;
                dfs(i, j); // 标记整个水塘
            }
        }
    }

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

复杂度

每个格子最多入队一次，时间和空间复杂度均为 O(nm)O(nm)。

总结

统计连通块的固定模式是“发现一个未访问目标点，答案加一，再搜索并标记整个连通块”。本题只是把邻接方向改成八方向。