八连通洪泛填充：扫描棋盘遇到未访问的 W 就计数，并用迭代栈把它所在整片连通水洼就地从 W 改写成 .。
OJ: roj
题目 ID: 1249
难度:普及-
标签:搜索洪泛填充连通块网格python
创建: 2026-09-30 01:45
更新: 2026-10-05 06:54
题目描述
给定 W 表示有水、. 表示干燥，八连通（上下、左右及四条对角线）的 W 属于同一片水洼，求水洼总数。输入第一行 10 12 后接 3。
思路
八连通不是四连通，斜着相邻也算同一片。外层扫描棋盘，每遇到一个仍为 W 的格子就说明发现一片新水洼：答案加一，再从它出发用迭代栈洪泛，把整片连通水洼全部改写成 .，棋盘因此兼任访问标记。总复杂度
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 01:46
# update_at: 2026-09-30 01:46
import sys
WATER = 'W' # 有水
DRY = '.' # 干燥；同时用它把已访问的水格抹掉，省掉额外的 visited 表
OFFSETS = tuple(
(dr, dc)
for dr in (-1, 0, 1)
for dc in (-1, 0, 1)
if (dr, dc) != (0, 0)
) # 八连通：上、下、左、右 + 四条对角线，共 8 个方向
def flood(grid: list[bytearray], row: int, col: int) -> None:
"""从 (row, col) 出发做八连通洪泛，把整片水洼改成 DRY（原地标记已访问）。"""
grid[row][col] = ord(DRY)
stack = [(row, col)]
while stack:
r, c = stack.pop()
for dr, dc in OFFSETS:
nr, nc = r + dr, c + dc
# 越界判定合并成一次链式比较，比 0 <= nr < n and 0 <= nc < m 少一趟比较
if -1 < nr < len(grid) and -1 < nc < len(grid[0]) and grid[nr][nc] == ord(WATER):
grid[nr][nc] = ord(DRY)
stack.append((nr, nc))
def solve() -> None:
"""统计八连通 'W' 的连通块个数（水洼数）。"""
data = iter(sys.stdin.buffer.read().split())
rows = int(next(data)) # 题面的 N
cols = int(next(data)) # 题面的 M：只为顺序消费掉，行宽以每行 token 本身为准
grid = [bytearray(next(data)) for _ in range(rows)] # 每行是一个整体 token
ponds = 0
for r in range(rows):
for c in range(len(grid[r])):
if grid[r][c] == ord(WATER):
ponds += 1 # 每遇到一个尚未被洪泛吞掉的水格，就开出一片新水洼
flood(grid, r, c)
print(ponds)
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 06:55
* update_at: 2026-10-05 06:55
*/
#include <cstdio>
typedef long long ll;
const int MAXN = 115;
char grid[MAXN][MAXN]; // grid[1..n][1..m]：'W' 有水、'.' 干燥；访问过的 'W' 就地改成 '.' 当访问标记
int stack_r[MAXN * MAXN]; // 洪泛栈的行坐标，每格最多入栈一次，容量 n*m 足够
int stack_c[MAXN * MAXN]; // 洪泛栈的列坐标
ll n, m;
int main() {
scanf("%lld %lld", &n, &m);
for (ll i = 1; i <= n; i++) {
scanf("%s", grid[i] + 1);
}
ll ponds = 0;
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j <= m; j++) {
if (grid[i][j] != 'W') {
continue;
}
ponds++; // 遇到一个还没被洪泛吞掉的水格，就是一片新水洼
// 迭代洪泛：栈里放待扩展的格子坐标
ll top = 0;
grid[i][j] = '.'; // 入栈前就标记，保证每个水格最多入栈一次
stack_r[top] = i;
stack_c[top] = j;
top++;
while (top > 0) {
top--;
ll r = stack_r[top];
ll c = stack_c[top];
// 八连通：行、列偏移各取 -1,0,1，排除 (0,0)
for (ll dr = -1; dr <= 1; dr++) {
for (ll dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) {
continue;
}
ll nr = r + dr;
ll nc = c + dc;
if (nr < 1 || nr > n || nc < 1 || nc > m) {
continue;
}
if (grid[nr][nc] != 'W') {
continue;
}
grid[nr][nc] = '.';
stack_r[top] = nr;
stack_c[top] = nc;
top++;
}
}
}
}
}
printf("%lld\n", ponds);
return 0;
}