题解 | 数水坑

import sys
n,m = map(int,input().split())
puddle = 0
grid = [list(sys.stdin.readline().strip()) for _ in range(n) ]
visited = [[False]*m for _ in range(n)]
dirs = [(-1,-1),(-1,0),(-1,1),
    (0,-1),         (0,1),
    (1,-1),(1,0),(1,1)]

# dfs版本
def dfs(x,y):
    visited[x][y] = True
    # 如果是水坑，则递归完所有相邻的w，并且标记
    for dx,dy in dirs:
        nx,ny = x+dx,y+dy
        if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and grid[nx][ny]=='W':
            dfs(nx,ny)

# bfs版本
def bfs(x,y):
    from collections import deque
    dq = deque([(x,y)])
    while dq:
        x,y = dq.popleft()
        for dx,dy in dirs:
            nx,ny = x+dx,y+dy
            if 0<=nx<n and 0<=ny<m and not visited[nx][ny] and grid[nx][ny]=='W':
                dq.append((nx,ny))
                visited[nx][ny]=1
                 
# 正常遍历
# for i in range(n):
#     for j in range(m):
#         if grid[i][j]=='W' and not visited[i][j]:
#             # dfs(i,j)
#             bfs(i,j)
#             puddle +=1

# 压缩优化
# 避免对普通格子计算visited
water_position=[(x,y) for x in range(n) for y in range(m) if grid[x][y]=='W']
for i,j in water_position:
    if not visited[i][j]:
        bfs(i,j)
        puddle +=1
# 进一步压缩：
# 减少visited的内存占用
# visited = set()
print(puddle)