题解 | 数水坑

import sys
from collections import deque

data = sys.stdin.read().strip().split()
it = iter(data)
n = int(next(it))
m = int(next(it))
grid = []
for i in range(n):
    grid.append(list(next(it)))


def bfs(x, y):
    offset = ((1, 0), (-1, 0), (0, 1), (0, -1), (-1, -1), (1, -1), (-1, 1), (1, 1))
    stack = deque()
    stack.append((x, y))
    grid[x][y] = "."
    while stack:
        x, y = stack.popleft()
        for dx, dy in offset:
            new_x = x + dx
            new_y = y + dy
            if 0 <= new_x < n and 0 <= new_y < m and grid[new_x][new_y] == "W":
                stack.append((new_x, new_y))
                grid[new_x][new_y] = "."


ans = 0
for i in range(n):
    for j in range(m):
        if grid[i][j] == "W":
            bfs(i, j)
            ans += 1
print(ans)