本文共 1626 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要计算一个 NxM 网格中连通的水坑的数量。每个水坑由相连的水格子组成，相连包括上下左右八个方向。我们可以使用广度优先搜索（BFS）来遍历每个水坑，确保每个连通块只被计算一次。

方法思路

解决代码

import sysfrom collections import dequedef main():    # 读取输入    n, m = map(int, sys.stdin.readline().split())    grid = []    for _ in range(n):        line = sys.stdin.readline().strip()        grid.append([c == 'W' for c in line])        ans = 0  # 水坑的数量    for i in range(n):        for j in range(m):            if grid[i][j]:                # 使用BFS遍历这个连通块                queue = deque()                queue.append((i, j))                grid[i][j] = False  # 标记为已访问                while queue:                    x, y = queue.popleft()                    for dx in (-1, 0, 1):                        for dy in (-1, 0, 1):                            if dx == 0 and dy == 0:                                continue                            nx = x + dx                            ny = y + dy                            if 0 <= nx < n and 0 <= ny < m:                                if grid[nx][ny]:                                    grid[nx][ny] = False                                    queue.append((nx, ny))                ans += 1    print(ans)if __name__ == "__main__":    main()

代码解释

这种方法确保了每个连通块只被计算一次，时间复杂度为O(N*M)，适用于网格尺寸在1到100之间的情况。

转载地址：http://umtg.baihongyu.com/