【华为OD机考真题】智慧交通·路口最短时间问题（Python/JS）

一、题目假定街道是棋盘型的每格距离相等车辆通过每格街道需要时间均为 timePerRoad;街道的街口(交叉点)有交通灯灯的周期 T(lights[row][col])各不相同;车辆可直行、左转和右转其中直行和左转需要等相应T时间的交通灯才可通行右转无需等待。现给出 n*m个街口的交通灯周期以及起止街口的坐标计算车辆经过两个街口的最短时间,其中:1)起点和终点的交通灯不计入时间且可以任意方向经过街口2) 不可超出 nm个街口不可跳跃但边线也是道路(即 lights[0][0] - lights[0][1] 是有效路径)输入描述第一行输入 n 和 m以空格分隔之后 n 行输入 lights矩阵矩阵每行m个整数以空格分隔之后一行输入 timePerRoad之后一行输入 rowStart colStart以空格分隔最后一行输入 rowEnd colEnd以空格分隔输出描述lights[rowStart][colStart] 与 lights[rowEnd][colEnd] 两个街口之间的最短通行时间input 3 3 1 2 3 4 5 6 7 8 9 60 0 0 2 2 output 245二、解题思路状态空间 Dijkstra1. 为什么普通 BFS/Dijkstra 会失效在标准最短路中dist[r][c]表示到达 (r,c) 的最短时间。但在本题中到达 (r,c) 的“未来代价”取决于你是怎么来的。如果你从北边来车头朝南下一步想往东走 →→左转→→需等灯。如果你从西边来车头朝东下一步想往东走 →→直行→→需等灯。如果你从北边来车头朝南下一步想往西走 →→右转→→不等灯。结论状态必须扩展为(行, 列, 朝向)。朝向定义为到达该点时的车头方向即上一步的移动方向。方向编码0:上, 1:右, 2:下, 3:左。2. 算法流程初始化定义三维距离数组dist[n][m][4]初始化为无穷大。优先队列最小堆存入起点的 4 个可能状态(time0, rstart_r, cstart_c, dird)其中 d∈[0,3] 。Dijkstra 循环弹出当前时间最小的状态(t, r, c, in_dir)。遍历 4 个可能的下一步方向next_dir计算新坐标(nr, nc)。判断转向类型相对角度diff (next_dir - in_dir 4) % 4。diff 1右转→→wait 0。diff 2掉头→→ 跳过非最优。diff 0(直行) 或diff 3(左转) →→ 计算等待时间。若当前点是起点wait 0。否则wait (T - (t % T)) % T。更新new_time t wait timePerRoad。若new_time dist[nr][nc][next_dir]更新并入队。结果取终点(rowEnd, colEnd)在 4 个朝向下时间的最小值。3. 转向判断速查表假设方向编码0:上, 1:右, 2:下, 3:左当前朝向 (in)目标朝向 (next)差值 (next-in4)%4动作等待?上 (0)右 (1)1右转否上 (0)下 (2)2掉头跳过上 (0)左 (3)3左转是上 (0)上 (0)0直行是右 (1)下 (2)1右转否...............三、代码实现1. Python 实现Python 的heapq模块非常适合实现 Dijkstra 算法代码简洁易懂。import heapq import sys # 方向定义上(0), 右(1), 下(2), 左(3) # 对应坐标变化 (dr, dc) DIRS [(-1, 0), (0, 1), (1, 0), (0, -1)] def solve(): # 读取所有输入 input_data sys.stdin.read().split() if not input_data: return iterator iter(input_data) try: n int(next(iterator)) m int(next(iterator)) lights [] for _ in range(n): row [] for _ in range(m): row.append(int(next(iterator))) lights.append(row) time_per_road int(next(iterator)) r_start int(next(iterator)) c_start int(next(iterator)) r_end int(next(iterator)) c_end int(next(iterator)) except StopIteration: return # dist[r][c][dir] 初始化为无穷大 INF float(inf) dist [[[INF] * 4 for _ in range(m)] for _ in range(n)] # 优先队列(time, r, c, direction) pq [] # 起点初始化可以假设从任意方向到达起点或者第一步无等待 # 我们将起点的4个方向都加入队列时间为0 for d in range(4): dist[r_start][c_start][d] 0 heapq.heappush(pq, (0, r_start, c_start, d)) while pq: t, r, c, in_dir heapq.heappop(pq) # 如果当前取出的时间大于已记录的最短时间跳过 if t dist[r][c][in_dir]: continue # 尝试向4个方向移动 for next_dir in range(4): nr r DIRS[next_dir][0] nc c DIRS[next_dir][1] # 边界检查 if 0 nr n and 0 nc m: wait_time 0 # 规则起点交通灯不计入 if r r_start and c c_start: wait_time 0 else: # 计算转向差值 diff (next_dir - in_dir 4) % 4 if diff 1: # 右转无需等待 wait_time 0 elif diff 2: # 掉头通常不是最优解直接跳过 continue else: # 直行 (0) 或 左转 (3)需要等灯 cycle lights[r][c] if cycle 0: wait_time (cycle - (t % cycle)) % cycle else: wait_time 0 new_time t wait_time time_per_road if new_time dist[nr][nc][next_dir]: dist[nr][nc][next_dir] new_time heapq.heappush(pq, (new_time, nr, nc, next_dir)) # 结果是终点4个方向中的最小值 ans min(dist[r_end][c_end]) print(ans if ans ! INF else -1) if __name__ __main__: solve()2. JavaScript 实现Node.js 原生没有优先队列我们需要手动实现一个简单的 Min-Heap或者使用数组排序数据量小时可行但推荐 Heap。以下使用自定义 Heap 以保证效率。const readline require(readline); // 方向定义上(0), 右(1), 下(2), 左(3) const DR [-1, 0, 1, 0]; const DC [0, 1, 0, -1]; // 最小堆实现 class MinHeap { constructor() { this.heap []; } push(item) { this.heap.push(item); this._bubbleUp(this.heap.length - 1); } pop() { if (this.heap.length 0) return null; const top this.heap[0]; const end this.heap.pop(); if (this.heap.length 0) { this.heap[0] end; this._sinkDown(0); } return top; } isEmpty() { return this.heap.length 0; } _bubbleUp(idx) { const element this.heap[idx]; while (idx 0) { const parentIdx Math.floor((idx - 1) / 2); const parent this.heap[parentIdx]; if (element.time parent.time) break; this.heap[idx] parent; this.heap[parentIdx] element; idx parentIdx; } } _sinkDown(idx) { const length this.heap.length; const element this.heap[idx]; while (true) { let leftChildIdx 2 * idx 1; let rightChildIdx 2 * idx 2; let swapIdx null; if (leftChildIdx length) { if (this.heap[leftChildIdx].time element.time) { swapIdx leftChildIdx; } } if (rightChildIdx length) { const rightChild this.heap[rightChildIdx]; if ((swapIdx null rightChild.time element.time) || (swapIdx ! null rightChild.time this.heap[swapIdx].time)) { swapIdx rightChildIdx; } } if (swapIdx null) break; this.heap[idx] this.heap[swapIdx]; this.heap[swapIdx] element; idx swapIdx; } } } function solve() { const rl readline.createInterface({ input: process.stdin, output: process.stdout, terminal: false }); const lines []; rl.on(line, (line) { lines.push(line.trim()); }); rl.on(close, () { const tokens lines.join( ).split(/\s/).filter(t t ! ); if (tokens.length 0) return; let idx 0; const n parseInt(tokens[idx]); const m parseInt(tokens[idx]); const lights []; for (let i 0; i n; i) { const row []; for (let j 0; j m; j) { row.push(parseInt(tokens[idx])); } lights.push(row); } const timePerRoad parseInt(tokens[idx]); const rStart parseInt(tokens[idx]); const cStart parseInt(tokens[idx]); const rEnd parseInt(tokens[idx]); const cEnd parseInt(tokens[idx]); // 初始化距离数组 dist[n][m][4] const INF Number.MAX_SAFE_INTEGER; const dist Array.from({ length: n }, () Array.from({ length: m }, () Array(4).fill(INF)) ); const pq new MinHeap(); // 起点初始化 for (let d 0; d 4; d) { dist[rStart][cStart][d] 0; pq.push({ time: 0, r: rStart, c: cStart, dir: d }); } while (!pq.isEmpty()) { const { time: t, r, c, dir: inDir } pq.pop(); if (t dist[r][c][inDir]) continue; // 尝试4个方向 for (let nextDir 0; nextDir 4; nextDir) { const nr r DR[nextDir]; const nc c DC[nextDir]; if (nr 0 nr n nc 0 nc m) { let waitTime 0; if (r rStart c cStart) { waitTime 0; } else { const diff (nextDir - inDir 4) % 4; if (diff 1) { // 右转 waitTime 0; } else if (diff 2) { // 掉头跳过 continue; } else { // 直行 (0) 或 左转 (3) const cycle lights[r][c]; if (cycle 0) { waitTime (cycle - (t % cycle)) % cycle; } } } const newTime t waitTime timePerRoad; if (newTime dist[nr][nc][nextDir]) { dist[nr][nc][nextDir] newTime; pq.push({ time: newTime, r: nr, c: nc, dir: nextDir }); } } } } const ans Math.min(...dist[rEnd][cEnd]); console.log(ans INF ? -1 : ans); }); } solve();四、核心考点与避坑指南三维状态是关键很多考生只用了dist[r][c]导致无法区分“刚右转到达”和“刚直行到达”的状态从而算错等待时间。记住方向也是状态的一部分。等待时间公式陷阱正确公式(T - (t % T)) % T。错误写法T - (t % T)。当t是T的倍数时错误写法会得到T意味着要等一个完整周期而实际上应该是0刚好绿灯。外层% T至关重要。起点的特殊处理题目明确“起点交通灯不计入”。这意味着从起点出发的第一条边无论转向如何waitTime强制为 0。代码中通过if (r rStart c cStart)实现了这一逻辑。掉头的处理在网格图中原地掉头diff 2通常意味着走回头路不可能构成最短路径除非是死胡同且必须退回但本题是开放网格。为了优化性能可以直接continue跳过掉头情况。语言特性对比Pythonheapq库非常成熟元组比较天然支持多关键字代码极其精简。JavaScript需手动实现 Heap 或使用第三方库机考环境通常无网需手写。注意 JS 的大数处理和异步 IO 的读取方式。五、结语这道题是带状态约束的最短路径问题的经典变种。它不仅仅考察 Dijkstra 算法的背诵更考察将实际业务规则交通规则抽象为图论模型的能力。掌握“坐标 方向”的状态扩展技巧你就能轻松解决此类问题甚至扩展到更复杂的场景如不同车型速度不同、携带物品限制等。希望这篇博文能助你在机考中旗开得胜如果觉得有帮助欢迎点赞、收藏、关注获取更多OD机考算法真题解析