Grid as Graph網格圖

from collections import deque

DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]    # 上、下、左、右


def island_areas(grid):
    """四方向相連的 1 是一座島。回傳每座島的面積（依掃描順序），長度就是島嶼數。"""
    m, n = len(grid), len(grid[0])
    seen = [[False] * n for _ in range(m)]
    areas = []
    for r in range(m):
        for c in range(n):
            if grid[r][c] != 1 or seen[r][c]:
                continue
            seen[r][c] = True                 # 掃到沒走過的陸地：新島的起點
            queue, area = deque([(r, c)]), 0
            while queue:
                cr, cc = queue.popleft()      # 改成 queue.pop() 就是堆疊版，面積不變
                area += 1
                for dr, dc in DIRS:
                    nr, nc = cr + dr, cc + dc
                    # 先檢查邊界：Python 的 grid[-1] 不會報錯，會悄悄取到最後一列
                    if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1 and not seen[nr][nc]:
                        seen[nr][nc] = True   # 放入時就標記，同一格才不會被放入兩次
                        queue.append((nr, nc))
            areas.append(area)
    return areas


def nearest_exit(floor):
    """多源 BFS：每格走到最近的出口 E 要幾步。牆 # 與走不到的格子是 -1。"""
    m, n = len(floor), len(floor[0])
    dist = [[-1] * n for _ in range(m)]
    queue = deque()
    for r in range(m):
        for c in range(n):
            if floor[r][c] == "E":
                dist[r][c] = 0                # 所有出口一開始就在佇列裡，距離 0
                queue.append((r, c))
    while queue:
        r, c = queue.popleft()
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and floor[nr][nc] != "#" and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1  # 第一次被走到就是最短步數
                queue.append((nr, nc))
    return dist


if __name__ == "__main__":
    grid = [
        [1, 1, 0, 0, 0, 1],
        [1, 0, 0, 1, 0, 1],
        [0, 0, 1, 1, 0, 0],
        [0, 0, 0, 1, 0, 0],
        [1, 0, 0, 0, 0, 1],
    ]
    areas = island_areas(grid)
    print(len(areas), areas, max(areas))   # 5 [3, 2, 4, 1, 1] 4

    floor = ["E.#...",
             "..#.#.",
             "....#E",
             "##.##.",
             "#.#..."]
    for r, row in enumerate(nearest_exit(floor)):
        print(" ".join(" #" if floor[r][c] == "#" else f"{d:2}" for c, d in enumerate(row)))
    # 輸出（# 是牆；(4, 1) 被牆圍住，走不到任何出口，所以是 -1）：
    #  0  1  #  4  3  2
    #  1  2  #  5  #  1
    #  2  3  4  5  #  0
    #  #  #  5  #  #  1
    #  # -1  #  4  3  2