华为OD机试真题解析：BFS算法解决“欢乐的周末”最短路径问题

1. 项目概述从一道机试真题看算法实战最近在技术社区和求职圈里“华为OD机试”的热度一直居高不下。很多朋友在准备面试时都会把历年的机试真题当作重要的练兵场。今天我想和大家深入聊聊其中一道挺有意思的题目——“欢乐的周末”。这道题不仅频繁出现在各类机试真题的讨论中也因为它融合了基础的图论思想和实际的生活场景成为了检验候选人基础编码和问题建模能力的经典案例。简单来说“欢乐的周末”描述了一个典型的搜索问题在一个由网格表示的地图上有若干个人比如小华和小为和若干家餐厅。每个人只能向上下左右四个方向移动目标是找到那些能让所有人同时到达的餐厅位置。题目会给出地图大小、障碍物位置、人物和餐厅坐标我们需要计算出符合条件的餐厅数量。这听起来像是一个简单的BFS广度优先搜索应用但其中关于“同时到达”的定义、多源点搜索的处理以及效率优化都藏着不少值得琢磨的细节。无论是用C追求极致性能还是用Python讲究快速实现亦或是用Java构建清晰结构这道题都能很好地体现你的编程功底和思维习惯。2. 核心需求与问题建模拆解在动手写代码之前我们必须把题目要求彻底吃透并转化为清晰的计算机模型。很多同学栽跟头不是因为算法不会而是因为题意理解有偏差。2.1 题目场景还原与关键约束我们首先在脑子里构建出这个“周末觅食”的场景。想象一个M x N的网格就像一张城市地图网格单元状态每个格子可能是空地0、障碍物-1、人物位置如2代表小华3代表小为或餐厅位置1。移动规则每个人物每步只能向上、下、左、右四个方向移动到相邻的空地或餐厅格子不能穿越障碍物也不能走出地图边界。核心目标找出所有这样的餐厅——从小华和小为的位置出发都能通过一条路径抵达该餐厅并且他们到达该餐厅所需的步数即最短路径长度是相同的。这里有几个极易混淆的要点我必须重点强调注意“同时到达”指的是路径长度相等而不是要求他们像赛跑一样同时出发、同时刻到达。只要从各自起点到某个餐厅的最短距离数值相等这个餐厅就符合条件。他们完全可以在不同的时间点出发只要步数一样就行。另一个坑题目并未要求路径必须唯一也未要求路径不能交叉或共享。只要存在至少一条从每个人到餐厅的路径且最短路径长度相等即可。2.2 数学模型抽象与算法选型基于以上分析我们可以将问题抽象为输入一个M x N的矩阵grid以及标识了人物和餐厅的特定值。处理对每个人物位置计算其到地图上所有可达格子的最短距离。这本质上是一个多源点最短路径问题但源点只有两个小华和小为。输出遍历所有餐厅格子检查对于每个餐厅两个人物到它的最短距离是否都被计算出来即都可达且这两个距离值相等。统计满足条件的餐厅数量。算法选择思路为什么是BFS而不是DFS在无权图每一步代价相同中寻找最短路径BFS具有天然优势。BFS从起点一层层向外扩张第一次访问到某个节点时所经历的步数就是最短步数。DFS则需要遍历所有可能路径才能确定最短的那条效率低得多。单源BFS vs 多源BFS我们有两个明确的起点小华和小为。最直接的思路是对每个人物分别进行一次BFS生成两个独立的距离矩阵。这样逻辑清晰实现简单。虽然有多余的遍历但鉴于M和N通常不会巨大机试题常见范围两次BFS是完全可接受的。存储结构我们需要存储每个人物到每个格子的最短距离。可以用两个与grid同尺寸的二维数组dist1和dist2初始值设为-1表示不可达或未访问。在BFS过程中将步数记录进去。3. 核心算法实现与代码解析理论清晰后我们来看具体实现。我会以Python版本作为主线进行详细讲解因为它语法简洁易于理解思路然后再对比其他语言的关键点。Python版本追求的是思路的清晰和实现的快捷。3.1 数据结构与BFS模板设计首先我们设计BFS函数。它需要接收起点坐标、地图信息并返回一个距离矩阵。from collections import deque from typing import List def bfs(start_x: int, start_y: int, grid: List[List[int]]) - List[List[int]]: 从起点(start_x, start_y)进行BFS返回到达每个点的最短步数矩阵。 不可达点距离为-1。 m, n len(grid), len(grid[0]) # 初始化距离矩阵-1表示未访问/不可达 dist [[-1] * n for _ in range(m)] # 如果起点就是障碍直接返回根据题意人物不会在障碍上 if grid[start_x][start_y] -1: return dist queue deque() queue.append((start_x, start_y)) dist[start_x][start_y] 0 # 起点距离为0 # 四个方向向量上、下、左、右 directions [(-1, 0), (1, 0), (0, -1), (0, 1)] while queue: x, y queue.popleft() current_dist dist[x][y] for dx, dy in directions: nx, ny x dx, y dy # 检查新坐标是否合法、不是障碍、且未被访问过 if 0 nx m and 0 ny n: if grid[nx][ny] ! -1 and dist[nx][ny] -1: dist[nx][ny] current_dist 1 queue.append((nx, ny)) return dist关键点解析使用deque作为队列在Python中collections.deque的popleft()操作是O(1)用列表模拟队列的pop(0)是O(n)在BFS中性能差异巨大。距离矩阵初始化用-1同时表示“未访问”和“不可达”简化了逻辑。访问过后值更新为非负整数步数。方向数组用一个列表定义四个方向比写四个if语句更简洁不易出错。访问判断顺序先判断坐标合法性再判断是否为障碍和是否已访问。这个顺序很重要可以避免数组越界访问。3.2 主逻辑整合与餐厅判定有了BFS函数主函数就负责组织数据、调用BFS并统计结果。def happy_weekend(grid: List[List[int]]) - int: m, n len(grid), len(grid[0]) # 步骤1找到所有人物和餐厅的位置 people [] restaurants [] for i in range(m): for j in range(n): val grid[i][j] if val 2 or val 3: # 假设2和3代表不同的人 people.append((i, j)) elif val 1: # 餐厅 restaurants.append((i, j)) if len(people) ! 2: # 根据题意这里可能默认就是两个人否则需要处理异常或更多逻辑 return 0 # 步骤2分别计算每个人到所有点的距离 dist_maps [] for px, py in people: dist_map bfs(px, py, grid) dist_maps.append(dist_map) # 步骤3遍历所有餐厅检查条件 count 0 for rx, ry in restaurants: valid True target_dist None for i, dist_map in enumerate(dist_maps): d dist_map[rx][ry] if d -1: # 有一个人不可达该餐厅 valid False break if target_dist is None: target_dist d # 记录第一个人到餐厅的距离 elif d ! target_dist: # 后续人的距离与第一个人不相等 valid False break if valid: count 1 return count主逻辑要点预处理扫描先遍历一遍地图记录下所有人物和餐厅的坐标。这样在后续判断时就无需再次遍历整个地图来寻找餐厅。条件判断逻辑对于每个餐厅我们依次检查每个人物的距离矩阵。一旦发现某个人不可达距离为-1或者当前人的距离与之前记录的距离target_dist不相等就立刻标记为无效并跳出循环。这是一种短路评估可以提高效率。边界情况代码中假设了恰好有两个人。如果题目可能变化这里需要增加更健壮的判断。3.3 多语言实现关键差异与技巧虽然算法核心一致但不同语言在实现时有其惯用写法和优化点。C实现要点队列使用std::queuestd::pairint, int。距离存储通常使用vectorvectorint初始化时可以用INT_MAX或-1表示未访问。性能C版本通常最快。要注意传递大型vector时尽量使用引用避免拷贝。代码风格结构清晰常将BFS封装为函数主函数内使用auto和范围for循环 (for (auto row : grid)) 让代码更现代。Java实现要点队列使用LinkedListint[]或ArrayDequeint[]作为Queue。距离存储使用int[][]数组。方向数组可以定义为int[][] dirs {{-1,0},{1,0},{0,-1},{0,1}};。特性代码结构严谨通常定义为一个Solution类包含方法。要注意Java中数组是对象dist数组需要显式初始化。JavaScript (Node.js) 实现要点队列用数组模拟但要注意shift()操作在V8引擎中可能不是O(1)。对于性能要求高的场景可以自己实现一个简单的队列类或者使用[head, tail]指针。距离存储使用二维数组。输入处理机试环境下的JS输入处理通常是难点需要熟悉readline模块按行读取并解析数据。语法使用const/let箭头函数解构赋值等ES6特性可以让代码更简洁。实操心得在机试的紧张环境下选择你最熟悉的语言。Python胜在代码量少思路表达快C胜在绝对性能和控制力Java胜在稳健和强大的IDE提示JS则要特别注意输入输出格式。先把核心逻辑写对再考虑优化。4. 测试用例设计与边界情况分析写完代码只是第一步设计全面的测试用例才能确保代码的健壮性。很多同学的程序在简单用例上通过却败在了边界情况上。4.1 常规测试用例基础用例小地图人物和餐厅路径清晰。输入 3 3 0 0 0 2 0 1 3 0 0 输出1 (餐厅(1,2)距离两人都是2步)无解用例有餐厅但有人无法到达或距离不等。输入 3 3 2 -1 1 0 -1 0 3 0 0 输出0 (小华被障碍挡住无法到达任何餐厅)多餐厅筛选多个餐厅只有部分满足条件。输入 4 4 0 0 0 1 2 0 -1 0 0 -1 0 0 3 0 0 1 输出1 (只有右下角的餐厅满足条件)4.2 边界与极端情况这些是真正考验代码鲁棒性的地方最小地图1x1网格且该格子就是餐厅和两个人(通常人物和餐厅是不同值这种输入可能非法但代码要能处理而不崩溃)。满障碍地图除了人物格子其余全是-1输出应为0。人物起点即餐厅如果某个人物初始位置就在一个标为1的格子上虽然题目可能不允许那么他到该餐厅的距离是0。需要和另一个人的距离比较。大地图性能例如100x100的全空地地图两个人分处对角餐厅在中间。两次BFS要能快速完成。这时BFS的O(M*N)复杂度是可靠的。输入格式验证机试中需要严格遵循题目规定的输入格式例如先输入M N再输入M行数据。读取代码要能正确处理。避坑技巧在本地调试时不要只用手算的简单用例。构造上述边界用例并用打印中间结果如两个人的距离矩阵的方式一步步跟踪程序状态能帮你快速定位逻辑错误。例如在BFS结束后打印出dist矩阵看看是否和你预期的最短距离一致。5. 算法优化与思路拓展在确保正确性的基础上我们可以思考一下是否有优化空间以及这道题相关的变体。5.1 潜在优化点分析双向BFSBi-directional BFS对于单源点找固定目标的最短路径双向BFS可以从起点和终点同时开始搜索相遇时即找到路径能显著减少搜索空间。但在这道题中我们的目标是计算起点到所有点的距离而不是到某一个特定点所以双向BFS不适用。多源BFSMulti-source BFS一次性计算我们可以修改BFS初始时将两个人的起点都加入队列并记录每个格子是被谁、在什么时候访问的。但这需要更复杂的状态记录格子被两个人访问的步数实现起来比两次独立的BFS更复杂且容易出错。在只有两个源点的情况下收益不大代码清晰度下降不推荐。早期剪枝在统计结果时如果我们发现某个餐厅对于第一个人就不可达那么根本不需要查询第二个人到该餐厅的距离。我们的代码已经通过“短路评估”实现了这一点。空间优化如果地图非常大两个MxN的距离矩阵可能占用较多内存。但考虑到机试约束这通常不是瓶颈。极端情况下可以尝试只存储必要的距离信息例如只记录餐厅格子的距离。结论对于这道题两次清晰的单源BFS是最佳实践。它时间复杂度是O(2 * M * N)即O(M*N)空间复杂度是O(M*N)完全在合理范围内。优化应优先保证代码正确、可读而非追求极致的常数时间优化。5.2 相关变体题目思维延伸理解这道题的解法后可以轻松应对一系列变体变体1找到任意一个欢乐餐厅。不需要统计数量找到一个即可。可以在遍历餐厅时找到第一个符合条件的就返回。变体2计算所有人到某个餐厅的最短路径和。这就是更经典的多源BFS问题初始化队列时放入所有人的起点最终距离矩阵记录的就是到达每个点的最近的那个人或某种聚合信息如最小步数。但本题要求的是“距离相等”而非“和最小”或“最大最小”所以不同。变体3路径上存在不同代价。如果网格不再是简单的空地/障碍而是每个格子有通过代价如时间、花费那么就需要使用Dijkstra算法或优先队列BFS来求单源最短路径。变体4更多人参与。如果有K个人思路完全一样进行K次BFS然后检查每个餐厅是否满足所有K个人的距离都相等。复杂度变为O(K * M * N)。掌握BFS解决网格最短路径问题的核心模板就能以不变应万变。模板包括队列定义、距离矩阵初始化、方向数组、入队出队循环、以及合法的邻接点判断。6. 机试实战策略与调试技巧最后结合这道题聊聊在华为OD或其他公司机试中的实战策略。6.1 时间分配与解题步骤审题5分钟绝对不要跳过用笔或注释标记出所有输入输出格式、关键约束如“同时到达”的定义、移动方向、障碍物。像“欢乐的周末”这种题目必须在纸上画出几个小例子验证自己的理解。思路设计10分钟确定算法核心本题即BFS设计数据结构距离矩阵想好主函数流程找点-BFS-统计。在脑子里或草稿上过一遍简单用例和边界用例。编码实现20-25分钟按照设计将代码模块化地写出来。先写BFS函数并确保其正确性可以先用一个简单用例测试。再写主逻辑。使用清晰的变量名。测试调试10-15分钟这是最关键的一步。不要只依赖题目给的样例。自测小用例用你审题时画的例子。测试边界用例地图大小为1全障碍人物紧挨餐厅等。打印调试在机试环境中printf/cout/print是你的好朋友。打印出距离矩阵一眼就能看出BFS计算是否正确。检查提交5分钟检查是否有拼写错误数组大小是否开够输入读取循环是否正确。最后提交。6.2 常见错误排查清单如果在调试时发现结果不对可以按这个清单排查输入读取错误是最常见的错误之一。确认M和N读取正确确认读取网格的循环次数是M次。方向数组越界在BFS中访问(nx, ny)前必须检查0 nx m and 0 ny n。障碍物判断逻辑grid[nx][ny] ! -1这个条件是否包含了起点起点可能是2或3不是0但肯定不是-1所以我们的判断grid[nx][ny] ! -1是合理的。距离初始化dist矩阵是否用-1正确初始化了起点距离是否设置为0了队列状态是否在将新节点(nx, ny)加入队列之前就更新了它的dist值这是BFS防止重复入队的关键。餐厅判断逻辑在统计时是否错误地要求了“路径必须唯一”或误解了“同时”全局变量污染如果使用了全局变量在多次调用BFS函数时是否做了正确的重置更好的做法是让BFS函数返回新的距离矩阵。6.3 编码风格与可读性建议在机试中代码不仅是给机器跑的也是给阅卷人看的。清晰的代码结构能减少你自己的错误也可能在边界情况下赢得一些印象分。函数化将BFS封装成独立的函数。命名清晰dist_to_person1,restaurant_list比d1,list1好得多。注释关键步骤在复杂的逻辑判断或循环处写上简短注释。避免魔法数字用常量或变量代替2,3,1,-1等。例如PERSON_A 2,RESTAURANT 1。这道“欢乐的周末”就像一把尺子能量出你对基础搜索算法的掌握是否扎实对问题细节的把握是否精准。它不追求高深的算法但非常考验基本功和严谨性。希望这次的拆解不仅能帮你搞定这一道题更能让你建立起解决这一类网格搜索问题的信心和方法论。在机试和日常开发中这种化繁为简、严谨建模的能力永远是最宝贵的。