攀登深度優先搜尋之山，《代碼來臨》第 10 天

今天的挑戰解決了第 10 天的難題，一個類似於第 6 天的二維網格，但需要探索多條路徑。 這個謎題優雅地展示了深度優先搜尋 (DFS) 的強大功能。

AI 產生的拼圖插圖

地圖被表示為字典；鍵是 (x, y) 座標，值是表示高度的單位數整數 (0-9)，其中 9 表示峰值。 解析函數有效地處理了這個資料結構：

<code class="language-python">def parse(input: str) -> dict[tuple[int, int], int | None]:
    return {
        (x, y): int(item) if item.isdigit() else None
        for y, row in enumerate(input.strip().splitlines())
        for x, item in enumerate(row)
    }</code>

步道從步道起點（高度 0）上升到山頂（高度 9），每步高度增加 1。 next_step 函數標識有效的後續步驟：

<code class="language-python">TRAIL_MAX = 9

def next_step(
    topo_map: dict[tuple[int, int], int | None], x: int, y: int
) -> tuple[tuple[int, int], ...]:
    assert topo_map[(x, y)] != TRAIL_MAX

    return tuple(
        incoming
        for incoming in (
            (x + 1, y),
            (x, y + 1),
            (x - 1, y),
            (x, y - 1),
        )
        if (
            isinstance(topo_map.get(incoming), int)
            and isinstance(topo_map.get((x, y)), int)
            and (topo_map[incoming] - topo_map[(x, y)] == 1)
        )
    )</code>

路線起點（高度 0）使用 find_trailheads:

定位

<code class="language-python">TRAILHEAD = 0

def find_trailheads(
    topo_map: dict[tuple[int, int], int | None],
) -> tuple[tuple[int, int], ...]:
    return tuple(key for key, value in topo_map.items() if value == TRAILHEAD)</code>

解決方案的核心是climb函數，它實現了深度優先搜尋。 遵循維基百科對 DFS 的定義，我們在回溯之前充分探索每個分支。

深度優先搜尋的視覺表示

地圖點是我們的“節點”，我們一次上升一層高度。 climb 函數管理 DFS 流程：

<code class="language-python">def climb(
    topo_map: dict[tuple[int, int], int | None], trailheads: tuple[tuple[int, int], ...]
) -> dict[
    tuple[tuple[int, int], tuple[int, int]], tuple[tuple[tuple[int, int], ...], ...]
]:
    candidates: list[tuple[tuple[int, int], ...]] = [(head,) for head in trailheads]

    result = {}

    while candidates:
        current = candidates.pop()
        while True:
            if topo_map[current[-1]] == TRAIL_MAX:
                result[(current[0], current[-1])] = result.get(
                    (current[0], current[-1]), ()
                ) + (current,)
                break

            elif steps := next_step(topo_map, *current[-1]):
                incoming, *rest = steps

                candidates.extend([current + (step,) for step in rest])

                current = current + (incoming,)
            else:
                break

    return result</code>

else 子句的 break 處理死胡同，防止無限循環。 此函數傳回從每個步道起點到山頂的所有路徑。

第 1 部分統計了獨特的高峰目的地：

<code class="language-python">def part1(input: str) -> int:
    topo_map = parse(input)

    return len(climb(topo_map, find_trailheads(topo_map)))</code>

第 2 部分計算所有唯一路徑：

<code class="language-python">def part2(input: str) -> int:
    topo_map = parse(input)

    return sum(
        len(routes) for routes in climb(topo_map, find_trailheads(topo_map)).values()
    )</code>

雖然有替代方法（例如，將 Trailhead 偵測整合到解析中），但該解決方案的效能是可以接受的。 最近找工作的挫折並沒有澆熄我的精神；我仍然充滿希望。 如果您正在尋找中高階 Python 開發人員，請與我們聯絡。 直到下週！

以上是攀登深度優先搜尋之山，《代碼來臨》第 10 天的詳細內容。更多資訊請關注PHP中文網其他相關文章！