分享丨【算法题单】网格图（DFS/BFS/综合应用）

# 返回网格图 grid 每个连通块的大小
# 时间复杂度 O(mn)
def dfsGrid(grid: List[List[str]]) -> List[int]:
    m, n = len(grid), len(grid[0])
    vis = [[False] * n for _ in range(m)]

    # 返回当前连通块的大小
    def dfs(i: int, j: int) -> int:
        vis[i][j] = True
        size = 1
        for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):  # 左右上下
            # 这里 grid[x][y] == '.' 根据题意修改
            if 0 <= x < m and 0 <= y < n and grid[x][y] == '.' and not vis[x][y]:
                size += dfs(x, y)
        return size

    comp_size = []
    for i, row in enumerate(grid):
        for j, ch in enumerate(row):
            if ch != '.' or vis[i][j]:  # ch != '.' 根据题意修改
                continue
            size = dfs(i, j)
            comp_size.append(size)
    return comp_size

# 返回从 (start_x, start_y) 出发，到其余格子的最短距离
# 时间复杂度 O(mn)
def bfsGrid(grid: List[List[str]], start_x: int, start_y: int) -> List[List[int]]:
    m, n = len(grid), len(grid[0])
    dis = [[-1] * n for _ in range(m)]

    dis[start_x][start_y] = 0
    q = deque([(start_x, start_y)])

    while q:
        i, j = q.popleft()
        for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):  # 左右上下
            # 这里 grid[x][y] == '.' 根据题意修改
            if 0 <= x < m and 0 <= y < n and grid[x][y] == '.' and dis[x][y] < 0:
                dis[x][y] = dis[i][j] + 1
                q.append((x, y))

    return dis