【华为OD机考真题】智慧交通·路口最短时间问题 (Java/Go)

一、题目假定街道是棋盘型的每格距离相等车辆通过每格街道需要时间均为 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 不够在标准最短路问题中到达点 (r,c) 的最小时间是固定的。但在本题中到达 (r,c) 的代价依赖于你是从哪个方向来的。如果你从北边来车头朝南想去东边→→左转→→ 需等灯。如果你从西边来车头朝东想去东边→→直行→→ 需等灯。如果你从北边来车头朝南想去西边→→右转→→不等灯。显然即使到达同一个点 (r,c) 的时间相同如果朝向不同下一步的等待时间也会不同进而影响总时间。因此状态必须包含朝向。2. 状态定义定义状态为(r, c, dir)r, c当前所在的街口坐标。dir到达该点时的车头朝向即上一步的移动方向。编码0:上, 1:右, 2:下, 3:左。dist[r][c][dir]记录到达该状态的最小时间。3. 算法流程初始化创建三维数组dist[n][m][4]初始化为无穷大。将起点(rowStart, colStart)的 4 个可能朝向状态加入优先队列时间设为 0因为起点不计等待。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 (T - (t % T)) % T其中 Tlights[r][c]Tlights[r][c] 。特判若当前点是起点wait 0。更新状态new_time t wait timePerRoad。若new_time dist[nr][nc][next_dir]更新并入队。结果提取遍历终点(rowEnd, colEnd)的 4 个朝向状态取最小值即为答案。三、代码实现1. Java 实现import java.util.*; import java.io.*; public class Main { // 方向数组上(0), 右(1), 下(2), 左(3) private static final int[] DR {-1, 0, 1, 0}; private static final int[] DC {0, 1, 0, -1}; static class State implements ComparableState { int r, c, dir, time; public State(int r, int c, int dir, int time) { this.r r; this.c c; this.dir dir; this.time time; } Override public int compareTo(State o) { return Integer.compare(this.time, o.time); } } public static void main(String[] args) { Scanner sc new Scanner(System.in); if (!sc.hasNextInt()) return; int n sc.nextInt(); int m sc.nextInt(); int[][] lights new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { lights[i][j] sc.nextInt(); } } int timePerRoad sc.nextInt(); int rowStart sc.nextInt(); int colStart sc.nextInt(); int rowEnd sc.nextInt(); int colEnd sc.nextInt(); System.out.println(calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd)); } public static int calcTime(int[][] lights, int timePerRoad, int rowStart, int colStart, int rowEnd, int colEnd) { int n lights.length; int m lights[0].length; // dist[r][c][dir] 记录最小时间 int[][][] dist new int[n][m][4]; for (int i 0; i n; i) { for (int j 0; j m; j) { Arrays.fill(dist[i][j], Integer.MAX_VALUE); } } PriorityQueueState pq new PriorityQueue(); // 起点可以以任意方向“进入”或者理解为第一步没有前驱方向限制 // 这里我们将起点的4个方向都初始化为0并在扩展第一步时强制等待时间为0 for (int d 0; d 4; d) { dist[rowStart][colStart][d] 0; pq.offer(new State(rowStart, colStart, d, 0)); } while (!pq.isEmpty()) { State cur pq.poll(); if (cur.time dist[cur.r][cur.c][cur.dir]) continue; // 尝试向4个方向移动 for (int nextDir 0; nextDir 4; nextDir) { int nr cur.r DR[nextDir]; int nc cur.c DC[nextDir]; if (nr 0 || nr n || nc 0 || nc m) continue; int waitTime 0; // 规则1起点交通灯不计入时间 if (cur.r rowStart cur.c colStart) { waitTime 0; } else { // 计算转向类型 // diff 1: 右转, 0: 直行, 3: 左转, 2: 掉头 int diff (nextDir - cur.dir 4) % 4; if (diff 1) { // 右转无需等待 waitTime 0; } else if (diff 2) { // 掉头通常不是最短路径跳过 continue; } else { // 直行 (0) 或 左转 (3)需要等灯 int T lights[cur.r][cur.c]; if (T 0) { waitTime (T - (cur.time % T)) % T; } else { waitTime 0; } } } int newTime cur.time waitTime timePerRoad; if (newTime dist[nr][nc][nextDir]) { dist[nr][nc][nextDir] newTime; pq.offer(new State(nr, nc, nextDir, newTime)); } } } // 取终点四个方向的最小值 int ans Integer.MAX_VALUE; for (int d 0; d 4; d) { ans Math.min(ans, dist[rowEnd][colEnd][d]); } return ans Integer.MAX_VALUE ? -1 : ans; } }2. Go 实现package main import ( bufio container/heap fmt math os strconv strings ) // 方向上0, 右1, 下2, 左3 var dr []int{-1, 0, 1, 0} var dc []int{0, 1, 0, -1} type State struct { r, c, dir, time int } // 优先队列实现 type PriorityQueue []*State func (pq PriorityQueue) Len() int { return len(pq) } func (pq PriorityQueue) Less(i, j int) bool { return pq[i].time pq[j].time } func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] pq[j], pq[i] } func (pq *PriorityQueue) Push(x interface{}) { item : x.(*State) *pq append(*pq, item) } func (pq *PriorityQueue) Pop() interface{} { old : *pq n : len(old) item : old[n-1] *pq old[0 : n-1] return item } func main() { scanner : bufio.NewScanner(os.Stdin) // 读取 n, m if !scanner.Scan() { return } parts : strings.Fields(scanner.Text()) n, _ : strconv.Atoi(parts[0]) m, _ : strconv.Atoi(parts[1]) // 读取 lights 矩阵 lights : make([][]int, n) for i : 0; i n; i { scanner.Scan() rowParts : strings.Fields(scanner.Text()) lights[i] make([]int, m) for j : 0; j m; j { lights[i][j], _ strconv.Atoi(rowParts[j]) } } // 读取 timePerRoad scanner.Scan() timePerRoad, _ : strconv.Atoi(scanner.Text()) // 读取起点 scanner.Scan() startParts : strings.Fields(scanner.Text()) rowStart, _ : strconv.Atoi(startParts[0]) colStart, _ : strconv.Atoi(startParts[1]) // 读取终点 scanner.Scan() endParts : strings.Fields(scanner.Text()) rowEnd, _ : strconv.Atoi(endParts[0]) colEnd, _ : strconv.Atoi(endParts[1]) fmt.Println(calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd)) } func calcTime(lights [][]int, timePerRoad, rowStart, colStart, rowEnd, colEnd int) int { n : len(lights) if n 0 { return -1 } m : len(lights[0]) // dist[r][c][dir] dist : make([][][]int, n) for i : range dist { dist[i] make([][]int, m) for j : range dist[i] { dist[i][j] make([]int, 4) for k : range dist[i][j] { dist[i][j][k] math.MaxInt32 } } } pq : PriorityQueue{} heap.Init(pq) // 初始化起点 for d : 0; d 4; d { dist[rowStart][colStart][d] 0 heap.Push(pq, State{rowStart, colStart, d, 0}) } for pq.Len() 0 { cur : heap.Pop(pq).(*State) if cur.time dist[cur.r][cur.c][cur.dir] { continue } // 尝试4个方向 for nextDir : 0; nextDir 4; nextDir { nr : cur.r dr[nextDir] nc : cur.c dc[nextDir] if nr 0 || nr n || nc 0 || nc m { continue } waitTime : 0 // 起点特殊处理 if cur.r rowStart cur.c colStart { waitTime 0 } else { diff : (nextDir - cur.dir 4) % 4 if diff 1 { // 右转 waitTime 0 } else if diff 2 { // 掉头跳过 continue } else { // 直行 (0) 或 左转 (3) T : lights[cur.r][cur.c] if T 0 { waitTime (T - (cur.time % T)) % T } } } newTime : cur.time waitTime timePerRoad if newTime dist[nr][nc][nextDir] { dist[nr][nc][nextDir] newTime heap.Push(pq, State{nr, nc, nextDir, newTime}) } } } ans : math.MaxInt32 for d : 0; d 4; d { if dist[rowEnd][colEnd][d] ans { ans dist[rowEnd][colEnd][d] } } if ans math.MaxInt32 { return -1 } return ans }四、关键点总结与避坑指南状态维度是核心错误做法只记录dist[r][c]。这会导致无法判断当前是直行还是转弯从而算错等待时间。正确做法记录dist[r][c][dir]。虽然空间复杂度增加了4倍但对于 N,M≤9N,M≤9 的小规模数据完全可控。右转的逻辑判断利用模运算(next - cur 4) % 4可以优雅地判断转向1→→ 右转免等待。0→→ 直行。3→→ 左转。2→→ 掉头本题可忽略。起点的特殊性题目明确“起点交通灯不计入”这意味着从起点出发的第一步无论转向如何等待时间均为 0。代码中通过if (cur.r rowStart ...)进行了特判。等待时间公式务必使用(T - (t % T)) % T。很多人会漏掉外层的% T导致当t % T 0时计算出等待时间为T错误而实际上应该是0。语言选择建议Java类库丰富PriorityQueue开箱即用适合快速编写逻辑。Go执行效率极高内存占用低container/heap虽需少量样板代码但在处理大量状态扩展时性能优势明显。 五、结语这道题是典型的分层图最短路或称状态空间搜索问题。它考察了考生将实际物理约束朝向、红绿灯规则转化为图论模型的能力。掌握这种“坐标 附加状态”的建模思想不仅能解决本题还能应对诸如“携带钥匙开门”、“不同速度模式”等变种题目。希望这篇博文能帮助你彻底搞懂这道题如果觉得有用欢迎点赞、收藏、关注获取更多华为OD机试真题解析与算法干货