攀登深度优先搜索之山，《代码来临》第 10 天

wufei123 2025-01-26 阅读:60 评论:0

深入解析第十天难题：多路径深度优先搜索第十天难题延续了第六天的二维网格模式，但挑战升级为寻找多条路径。本文将详细阐述如何巧妙运用深度优先搜索算法（DFS）解决此问题。 copilot提供的AI拼图插图地图用一个字典表示，键为(x, y)...

深入解析第十天难题：多路径深度优先搜索

第十天难题延续了第六天的二维网格模式，但挑战升级为寻找多条路径。本文将详细阐述如何巧妙运用深度优先搜索算法（DFS）解决此问题。

攀登深度优先搜索之山，《代码来临》第 10 天 copilot提供的AI拼图插图

地图用一个字典表示，键为(x, y)坐标，值为该点的高度(0-9，9为峰值)。以下代码实现了地图解析：

PHP

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)
    }

路径查找规则：每一步高度必须增加1。代码如下：

PHP

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)
        )
    )

起点（高度为0的点）的查找函数：

PHP

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)

基于维基百科对深度优先搜索的定义：

深度优先搜索(DFS)是一种用于遍历或搜索树或图数据结构的算法。它从根节点开始，沿着每个分支尽可能远地探索，并在回溯之前遍历完所有分支。

攀登深度优先搜索之山，《代码来临》第 10 天 深度优先搜索动画示例（图片来自维基百科）

我们使用DFS算法实现爬升函数，寻找所有路径：

PHP

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

else 子句中的 break 用于处理路径走到死胡同的情况，避免无限循环。

爬升函数返回一个字典，键为(起点，终点)对，值为所有到达该终点的路径。

第一部分：计算可到达的独特峰值数量，即字典的键值对数量：

PHP

def part1(input: str) -> int:
    topo_map = parse(input)
    return len(climb(topo_map, find_trailheads(topo_map)))

第二部分：计算所有路径的总数，即所有路径数量的总和：

PHP

def part2(input: str) -> int:
    topo_map = parse(input)
    return sum(
        len(routes) for routes in climb(topo_map, find_trailheads(topo_map)).values()
    )