攀登深度优先搜索之山,《代码来临》第 10 天
今天的挑战解决了第 10 天的难题,一个类似于第 6 天的二维网格,但需要探索多条路径。 这个谜题优雅地展示了深度优先搜索 (DFS) 的强大功能。
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) }
步道从步道起点(高度 0)上升到山顶(高度 9),每步高度增加 1。 next_step
函数标识有效的后续步骤:
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)使用 find_trailheads
:
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)
解决方案的核心是climb
函数,它实现了深度优先搜索。 遵循维基百科对 DFS 的定义,我们在回溯之前充分探索每个分支。
深度优先搜索的视觉表示
地图点是我们的“节点”,我们一次上升一层高度。 climb
函数管理 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
处理死胡同,防止无限循环。 该函数返回从每个步道起点到山顶的所有路径。
第 1 部分统计了独特的高峰目的地:
def part1(input: str) -> int: topo_map = parse(input) return len(climb(topo_map, find_trailheads(topo_map)))
第 2 部分计算所有唯一路径:
def part2(input: str) -> int: topo_map = parse(input) return sum( len(routes) for routes in climb(topo_map, find_trailheads(topo_map)).values() )
虽然存在替代方法(例如,将 Trailhead 检测集成到解析中),但该解决方案的性能是可以接受的。 最近找工作的挫折并没有浇灭我的精神;我仍然充满希望。 如果您正在寻找中高级 Python 开发人员,请联系我们。 直到下周!
以上是攀登深度优先搜索之山,《代码来临》第 10 天的详细内容。更多信息请关注PHP中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

Python适合数据科学、Web开发和自动化任务,而C 适用于系统编程、游戏开发和嵌入式系统。 Python以简洁和强大的生态系统着称,C 则以高性能和底层控制能力闻名。

两小时内可以学到Python的基础知识。1.学习变量和数据类型,2.掌握控制结构如if语句和循环,3.了解函数的定义和使用。这些将帮助你开始编写简单的Python程序。

Python在游戏和GUI开发中表现出色。1)游戏开发使用Pygame,提供绘图、音频等功能,适合创建2D游戏。2)GUI开发可选择Tkinter或PyQt,Tkinter简单易用,PyQt功能丰富,适合专业开发。

2小时内可以学会Python的基本编程概念和技能。1.学习变量和数据类型,2.掌握控制流(条件语句和循环),3.理解函数的定义和使用,4.通过简单示例和代码片段快速上手Python编程。

Python在web开发、数据科学、机器学习、自动化和脚本编写等领域有广泛应用。1)在web开发中,Django和Flask框架简化了开发过程。2)数据科学和机器学习领域,NumPy、Pandas、Scikit-learn和TensorFlow库提供了强大支持。3)自动化和脚本编写方面,Python适用于自动化测试和系统管理等任务。

Python更易学且易用,C 则更强大但复杂。1.Python语法简洁,适合初学者,动态类型和自动内存管理使其易用,但可能导致运行时错误。2.C 提供低级控制和高级特性,适合高性能应用,但学习门槛高,需手动管理内存和类型安全。

要在有限的时间内最大化学习Python的效率,可以使用Python的datetime、time和schedule模块。1.datetime模块用于记录和规划学习时间。2.time模块帮助设置学习和休息时间。3.schedule模块自动化安排每周学习任务。

Python在自动化、脚本编写和任务管理中表现出色。1)自动化:通过标准库如os、shutil实现文件备份。2)脚本编写:使用psutil库监控系统资源。3)任务管理:利用schedule库调度任务。Python的易用性和丰富库支持使其在这些领域中成为首选工具。
