看到“智能驾驶”四个字很多准备机试的同学第一反应是是不是要考深度学习、目标检测、传感器融合其实机试真题里出现“智能驾驶”考的根本不是人工智能而是你能不能把一个听起来很复杂的业务场景抽象成一套确定性的搜索模型。说白了就是用最短路径、状态搜索、时间窗口这些东西解决一个带动态约束的寻路问题。这类题目在头部厂商的OD机试中出镜率一直不低。它把业务背景包装成“园区自动驾驶配送”“智能驾驶车辆调度”“自动驾驶车辆路径规划”但核心算法却非常固定网格寻路 时间维度上的状态扩展。我最近带的一位同学就在机试里碰到了类似的题他先用了二维BFS结果在动态障碍的用例上直接卡死后来重新把“时间”作为状态的一维才算把题目吃透。这篇文章就把这道题从审题、建模到Python/Java/C三种语言实现完整拆一遍帮助你真正理解这类“带时间窗的网格搜索”题。1. 题目到底在考什么从业务包装到搜索模型先给一道典型真题的原型描述。题目通常会这样写某园区部署了一辆自动驾驶配送车需要从园区左上角出发到达右下角的收货点。园区被划分为 N×M 的网格每个格子可能是空地、固定障碍或临时管制区域。配送车每一步可以向上、下、左、右四个方向移动一格也可以原地等待每走一步耗时 1 个时间单位。部分临时管制区域只在指定的时间区间内禁止通行其余时间可以正常通行。请问配送车最早什么时间能到达终点这个描述翻译过来就是一个“带时间维度的网格BFS问题”。注意关键词空地、固定障碍、临时管制、原地等待、时间区间。出题人把真实的自动驾驶场景抽象成了几个特定数据结构而你要做的不是去理解雷达怎么感知而是要识别出这是一个最短到达时间问题状态不仅包括“我在哪个格子”还包括“我现在是第几秒”。1.1 智能驾驶题在机试中的常见变形我把这几年机试里出现过的智能驾驶寻路题按算法套路分了个类整理成一张表方便你快速定位题目包装核心数据结构推荐算法固定障碍的最短路径二维网格BFS带时间管制区域的最短路三维状态行列时间BFS不同路段通行代价不同带权图Dijkstra多台车协同配送多源搜索/状态队列BFS剪枝大范围地图路径规划启发式搜索A*限时到达求可行路径最短路时间约束动态规划/二分表格里最关键的一行就是第二行带时间管制区域的最短路。这一行是很多人的分水岭。会二维BFS的人很多能意识到“时间要并进状态”的人才是真正做对这道题的人。1.2 出题人埋的坑二维visied数组会误杀最优解先说一个最常见的翻车点。假设你直接用二维BFSvisited[r][c]记录某个格子是否走过。这在纯静态障碍里没问题但一旦加了临时管制就会出错。举个例子。网格只有一行三列起点在 (0,0)终点在 (0,2)中间是 (0,1)。(0,1) 在时间区间 [1, 5] 内禁止通行。起点到终点显然只有一条路等到第 6 秒再通过 (0,1)。但如果你用二维 visited 数组在第 0 秒到达 (0,1) 时发现禁止通行于是这条路被标记为“不可走”等第 1 秒、第 2 秒……你的 BFS 永远没有机会再尝试进入 (0,1)因为 visited 已经把格子锁死了。哪怕你在代码里做了“等待”操作二维 visited 也会让等待变得毫无意义。解决办法只有一个状态必须扩展成三元组(row, col, time)。访问标记也要变成三维或者是(row, col, 时间取模后的值)。判断一个格子能不能走不仅要看它是不是固定障碍还要看当前时刻是不是在管制区间里。1.3 为什么“原地等待”是必须的动作可能有人会问题目没说一定允许原地等待那我把它当作可选项不就行了吗事实上如果动态管制区域堵住了唯一通道原地等待就是绕开管制的最优策略。你等一个周期可能比绕一大圈更快。所以我在代码里统一把“原地等待”实现成一个方向为零的移动坐标不变时间加一。这是一种很自然的处理方式把等待和移动统一成“每个时刻必须做一个动作”的离散事件模型。这既符合真实自动驾驶中“低速巡航/等待指令”的语义又方便代码统一实现。2. 状态设计与算法选型为什么BFS够用又在什么情况下不够明确了状态是(row, col, time)接下来就是算法选型。这道题里每个动作代价都是 1 个单位时间无论是移动一格还是原地等待代价相同。因此 BFS 第一次到达终点的路径就是最早到达时间的路径。这可以说是最直观、最不容易出错的选择。2.1 动态障碍的判定函数要实现动态障碍最好把“当前时间能不能进入某个格子”抽象成一个独立的函数。伪代码如下bool canEnter(row, col, time): 越界判定 如果格子是固定障碍返回 false 如果格子存在管制窗口且 time 落在窗口内返回 false 返回 true这个函数一旦写好BFS 的主体逻辑就非常干净了。注意你还需要判断起点和终点本身是否在管制窗口内。很多人在终点上翻车就是因为只判断了中途格子忽略了终点在某个时刻被管制的情况。2.2 等待会让状态爆炸吗把等待当成一个动作后理论上你可以在某个格子无限等待下去。如果不加任何约束状态会变成无限多。好在机试数据通常不会这样刁难你。常见做法是加一个时间上限MAX_T比如N * M * 2 最大管制区间右端点。这个上限在工程上是合理的因为最优路径不太可能超过普通最短路径长度的若干倍如果超过说明这道题的数据本身有问题。另一个更优雅的做法是如果管制窗口是周期性的那么visited[row][col][time % period]就能压缩状态。但大部分机试题目里管制窗口是离散的单个区间直接用三维 visited 和合理的时间上限即可。面试时能主动提出周期压缩方案会是一个加分项。2.3 什么时候应该升级成Dijkstra虽然 BFS 在这道题里够用但如果在追问环节面试官把代价改成非均匀的——比如上坡路段耗时 2、下坡路段耗时 1或者某条车道要额外消耗 3 个时间单位BFS 就不成立了。遇到这种情况你应该把状态图的边权改成非负权用 Dijkstra 处理。这也是为什么我建议备考时不要把“做完题”当成终点。你应该在稿纸上再问自己一句如果移动代价不统一代码哪一行要改改完后Dijkstra 用优先队列存储(当前时间, row, col)松弛条件从“第一次访问”变成“时间更短才更新”本质上只换了一个容器和更新规则。3. Python/Java/C三种语言的完整实现与逐段拆解下面直接给三套完整代码。我刻意保持了核心逻辑一致方便对照学习。三种语言的差异主要体现在数据结构、内存管理、代码风格的取舍上。3.1 Python实现原型验证最快from collections import deque def min_arrival_time(grid, ban_windows): grid: 二维字符数组 S 起点E 终点. 空地# 固定障碍 ban_windows: dict key: (r, c) value: [(start_time, end_time), ...]闭区间 [start, end] rows, cols len(grid), len(grid[0]) start end None for i in range(rows): for j in range(cols): if grid[i][j] S: start (i, j) elif grid[i][j] E: end (i, j) if not start or not end: return -1 # 合理的时间上限普通最短路长度 最大的管制区间宽度再加一些余量 max_wait 0 for r in range(rows): for c in range(cols): if (r, c) in ban_windows: for start_t, end_t in ban_windows[(r, c)]: max_wait max(max_wait, end_t - start_t 1) max_t 2 * rows * cols max_wait 3 directions [(0, 0), (1, 0), (-1, 0), (0, 1), (0, -1)] # 等待 四方向 def can_enter(r, c, t): if not (0 r rows and 0 c cols): return False if grid[r][c] #: return False if (r, c) in ban_windows: for start_t, end_t in ban_windows[(r, c)]: if start_t t end_t: return False return True visited set() q deque() q.append((start[0], start[1], 0)) visited.add((start[0], start[1], 0)) while q: r, c, t q.popleft() if (r, c) end: return t if t max_t: continue for dr, dc in directions: nr, nc, nt r dr, c dc, t 1 if not can_enter(nr, nc, nt): continue if (nr, nc, nt) in visited: continue visited.add((nr, nc, nt)) q.append((nr, nc, nt)) return -1Python版本的核心优势是写得快、试错成本低。visited直接用一个集合存元组逻辑一目了然。唯一的问题是元组集合在状态量大的时候会占用较多内存但在机试数据规模下通常可接受。这段代码里的can_enter是核心抽象建议优先写好它再写主循环。3.2 Java实现工程化与容器选型import java.util.*; public class AutoDriveSearch { private static class State { int r, c, t; State(int r, int c, int t) { this.r r; this.c c; this.t t; } } // banWindows 用数组表示每行是 [row, col, start, end] public static int minArrivalTime(char[][] grid, int[][] banWindows) { int rows grid.length; int cols grid[0].length; int[] start null, end null; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] S) start new int[]{i, j}; else if (grid[i][j] E) end new int[]{i, j}; } } if (start null || end null) return -1; // 计算合理的时间上限 int[] maxWait {0}; for (int[] w : banWindows) { maxWait[0] Math.max(maxWait[0], w[3] - w[2] 1); } int maxT 2 * rows * cols maxWait[0] 3; // visited[r][c][t] 是本题的关键 boolean[][][] visited new boolean[rows][cols][maxT 1]; int[] dr {0, 1, -1, 0, 0}; int[] dc {0, 0, 0, 1, -1}; DequeState queue new ArrayDeque(); queue.offer(new State(start[0], start[1], 0)); visited[start[0]][start[1]][0] true; while (!queue.isEmpty()) { State cur queue.poll(); if (cur.r end[0] cur.c end[1]) return cur.t; if (cur.t maxT) continue; int nextR cur.r, nextC cur.c, nextT cur.t 1; // 待一步原地等待 if (nextT maxT canEnter(nextR, nextC, nextT, grid, banWindows, rows, cols) !visited[nextR][nextC][nextT]) { visited[nextR][nextC][nextT] true; queue.offer(new State(nextR, nextC, nextT)); } for (int k 1; k 4; k) { int nr cur.r dr[k]; int nc cur.c dc[k]; if (canEnter(nr, nc, nextT, grid, banWindows, rows, cols) !visited[nr][nc][nextT]) { visited[nr][nc][nextT] true; queue.offer(new State(nr, nc, nextT)); } } } return -1; } private static boolean canEnter(int r, int c, int t, char[][] grid, int[][] banWindows, int rows, int cols) { if (r 0 || r rows || c 0 || c cols) return false; if (grid[r][c] #) return false; for (int[] w : banWindows) { if (w[0] r w[1] c w[2] t t w[3]) { return false; } } return true; } }Java版的选型要点是ArrayDeque而非LinkedList。在这个场景下队列的 offer/poll 操作非常频繁ArrayDeque整体性能更好内存碎片也更少。三维boolean[][][]相比HashMap或编码成整数的Set在可读性上是最好的也最容易在机试环境里手写。如果你的格子规模在几百乘几百三维数组完全扛得住。3.3 C实现性能与内存布局的取舍#include bits/stdc.h using namespace std; struct State { int r, c, t; }; struct BanWindow { int r, c, start, end; }; bool canEnter(int r, int c, int t, const vectorstring grid, const vectorBanWindow bans) { int rows grid.size(), cols grid[0].size(); if (r 0 || r rows || c 0 || c cols) return false; if (grid[r][c] #) return false; for (const auto w : bans) { if (w.r r w.c c w.start t t w.end) { return false; } } return true; } int minArrivalTime(const vectorstring grid, const vectorBanWindow bans) { int rows grid.size(), cols grid[0].size(); State start; bool hasStart false; // 找起点终点 for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (grid[i][j] S) { start {i, j, 0}; hasStart true; } if (grid[i][j] E) {} } } if (!hasStart) return -1; int maxWait 0; for (const auto w : bans) maxWait max(maxWait, w.end - w.start 1); int maxT 2 * rows * cols maxWait 3; vectorvectorvectorbool visited(rows, vectorvectorbool(cols, vectorbool(maxT 1, false))); queueState q; q.push(start); visited[start.r][start.c][0] true; int dr[5] {0, 1, -1, 0, 0}; int dc[5] {0, 0, 0, 1, -1}; while (!q.empty()) { State cur q.front(); q.pop(); if (grid[cur.r][cur.c] E) return cur.t; if (cur.t maxT) continue; for (int k 0; k 5; k) { int nr cur.r dr[k]; int nc cur.c dc[k]; int nt cur.t 1; if (!canEnter(nr, nc, nt, grid, bans)) continue; if (visited[nr][nc][nt]) continue; visited[nr][nc][nt] true; q.push({nr, nc, nt}); } } return -1; }C 的实现思路和前面一致只是把代码写得“更硬”一些。这里我用了vectorvectorvectorbool虽然比 int 数组稍慢但写起来不容易错。追求极限性能的人可以改成vectorvectorvectorint用 0/1 标记。另一个小优化是把visited的三维索引平铺成一维数组idx (r * cols c) * (maxT 1) t这样内存访问更连续缓存命中率也会更高。3.4 三份代码的差异对比维度PythonJavaC状态存储set 去重元组三维 boolean 数组三维 vector队列collections.dequeArrayDequestd::queue等待动作(0,0) 移动单独处理五方向统一处理内存占用中等高可控适合场景快速验证思路机试标准答题性能压力较大时我个人建议备考顺序是先用 Python 把思路跑通再用 Java 写一份适合机试的版本最后用 C 至少把主体逻辑写一遍。这样三种语言的切换能力就都有了。4. 用例推演与边界测试亲手把正确性“锤”一遍代码写完不是终点必须跑用例。下面这个例子能同时验证等待机制、绕路机制和动态管制逻辑。4.1 含动态管制的经典用例网格如下S . # . . . . . X . . X . . . . . . . E其中X表示带管制窗口的格子其余.为空地#是固定障碍。假设坐标为 (1,3) 的X在时间区间 [2,4] 禁止通行坐标为 (2,1) 的X在时间区间 [1,10] 禁止通行除了以上两个其余格子始终可通行手动推演时你可以发现如果完全绕开 (1,3)路径长度会变大如果不绕可以走到 (1,3) 附近等待到第 5 秒再通过。这个用例跑出来后最早到达时间就和“永远绕路”的答案不同能有效防止你把题做成纯静态最短路。4.2 边界条件速查表场景期望结果常用测试办法起点或终点不存在-1单独测试起点终点重合0直接返回 0终点在固定障碍内-1检查终点固定障碍终点在管制窗口内且无其他路需要等到窗口结束验证等待路径起点本身在管制窗口内不能在管制时出发要在 t0 判断起点可进所有路径被固定障碍堵死-1最终队列耗尽4.3 最容易挂掉的五个细节第一终点判断的时机。我每次从队列弹出状态时判断终点这没问题。但如果你在“生成下一步状态”时判断就可能提前把终点放进去而不检查其可进性导致终点在管制时间被误入。第二visited的维度要跟maxT对齐数组越界在 Java 里直接抛异常在 C 里是未定义行为极难排查。第三等待动作不能丢丢了动态管制用例必错。第四时间上限设得太小会把原本有解的用例误判为 -1。第五坐标方向搞反尤其是行和列的对应关系这种错误往往要过好几组数据才能发现很浪费时间。5. 面试官追问与考点延伸从 BFS 到多车调度机试里写完核心代码后面试官经常追加追问。这些问题往往才是区分“会做题”和“真懂原理”的关键。5.1 如果移动代价不再是 1怎么办如果有的格子耗时为 2说明状态图的边权不同了。此时应该切换到 Dijkstra 算法用优先队列取最小时间。Java 里可以用PriorityQueueStatePython 里用heapqC 里用priority_queue。核心改动是状态从“第一次访问就确定最优”变成“只有当前时间更短才更新”。5.2 如果多个配送车同时出发怎么处理多车问题可以看作多源 BFS把所有车的起点同时压入队列最先到达终点的车就是最优解。但更复杂的版本还有“多车不能同时占同一格”“任务需要按顺序完成”这种就需要把任务序列也编码进状态。我备考时遇到这样的追问一般先画状态转移图再决定用 BFS 还是 DP不要直接写代码。5.3 如果管制窗口非常大状态数爆炸状态数 格子数 × 时间上限。如果时间上限是几千三维 visited 也没问题如果是几万就要考虑状态压缩。一种做法是离散化时间只在“管制开始前/结束后”这些关键时间点建边。另一种是将所有管制窗口右端点排序用事件驱动的方式推进搜索。这种优化平时不用写但能讲出思路面试官对你的评价会明显高一个档次。5.4 这类题和真实自动驾驶的关系真实场景里车辆不会在网格上盲目搜索而是有全局路径规划和高精地图。但机试题的抽象精髓在于把连续世界离散化把时间约束作为状态的一部分。你可以把它理解成“决策规划”的最小模型。做懂这道题再去理解真实系统里的 RRT、A *、时空走廊这些概念会发现底层逻辑其实是相通的。6. 备考建议与个人经验三语言切换的实践技巧刷这种多语言真题我强烈建议你用“同题三写”的方式拿到一道题先用 Python 快速写一版再用 Java 写一版适合面试的最后用 C 至少完成主体搜索逻辑。这个过程不是重复劳动而是帮你在头脑中建立一套“语言无关的算法模板”。到了考场上你真正要拼的不是“会不会”而是“写得够不够快、够不够稳”。一个小技巧是拿一套自己的模板代码把canEnter、visited、队列声明、方向数组这些高频片段背到形成肌肉记忆。机试时间紧张如果每个细节都要临时想很容易超时。我个人的习惯是先把状态定义写在稿纸上再写主循环最后补边界判断。这样顺序清晰也减少了漏判。最后提醒一句遇到智能驾驶、无人机配送、仓储机器人这类题目时不要被名词吓住。先找“网格”“时间”“最短路径”这些关键词锁定算法类型然后果断动手建模。模型对了代码只是时间问题。我自己的体会是这类题最值钱的地方不是那个标准答案而是你推演状态、处理边界、切换语言实现的过程。把这些基本功练扎实了别说是智能驾驶再换个包装你也一眼就能看穿它本来的样子。
