深入解析第十天难题：多路径深度优先搜索
第十天难题延续了第六天的二维网格模式，但挑战升级为寻找多条路径。本文将详细阐述如何巧妙运用深度优先搜索算法（DFS）解决此问题。
copilot提供的AI拼图插图
地图用一个字典表示，键为(x, y)坐标，值为该点的高度(0-9，9为峰值)。以下代码实现了地图解析：
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。代码如下：
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的点）的查找函数：
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)是一种用于遍历或搜索树或图数据结构的算法。它从根节点开始，沿着每个分支尽可能远地探索，并在回溯之前遍历完所有分支。
深度优先搜索动画示例（图片来自维基百科）
我们使用DFS算法实现爬升函数，寻找所有路径：
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 用于处理路径走到死胡同的情况，避免无限循环。
爬升函数返回一个字典，键为(起点，终点)对，值为所有到达该终点的路径。
第一部分：计算可到达的独特峰值数量，即字典的数量：
def part1(input: str) -> int: topo_map = parse(input) return len(climb(topo_map, find_trailheads(topo_map)))
登录后复制
第二部分：计算所有路径的总数，即所有路径数量的总和：
def part2(input: str) -> int: topo_map = parse(input) return sum( len(routes) for routes in climb(topo_map, find_trailheads(topo_map)).values() )
登录后复制
总结：本文详细介绍了使用深度优先搜索算法解决第十天难题的完整过程，并对代码进行了优化和解释。 通过对算法和代码的深入分析，展现了高效解决多路径搜索问题的思路。 最后，个人求职经历的分享也为文章增添了一丝人文色彩。
以上就是攀登深度优先搜索之山，《代码来临》第 10 天的详细内容，更多请关注php中文网其它相关文章！
微信扫一扫打赏
支付宝扫一扫打赏
