)
一、题目假定街道是棋盘型的每格距离相等车辆通过每格街道需要时间均为 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. 为什么普通 Dijkstra 不够在标准最短路中dist[r][c]表示到达 (r,c) 的最短时间。但在本题中到达 (r,c) 的“未来代价”取决于你是从哪个方向来的。从北来车头朝南想去东→→左转→→需等灯。从西来车头朝东想去东→→直行→→需等灯。从北来车头朝南想去西→→右转→→不等灯。结论状态必须定义为(行, 列, 朝向)。朝向定义为到达该点时的车头方向即上一步的移动方向。方向编码0:上, 1:右, 2:下, 3:左。距离数组dist[n][m][4]。2. 算法流程初始化定义三维数组dist[n][m][4]初始化为INT_MAX。优先队列最小堆存入起点的 4 个可能状态(time0, r, c, dir)。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直行是 三、C 代码实现C 的priority_queue默认是大顶堆需要通过greater或自定义比较器改为小顶堆。以下代码使用了tuple和vector结构清晰效率极高。#include iostream #include vector #include queue #include tuple #include climits #include algorithm using namespace std; // 方向定义上(0), 右(1), 下(2), 左(3) // 对应坐标变化 (dr, dc) const int DR[] {-1, 0, 1, 0}; const int DC[] {0, 1, 0, -1}; // 状态结构体时间行列朝向 struct State { int time; int r; int c; int dir; // 重载 运算符用于优先队列的小顶堆排序 bool operator(const State other) const { return time other.time; } }; int calcTime(const vectorvectorint lights, int timePerRoad, int rowStart, int colStart, int rowEnd, int colEnd) { int n lights.size(); if (n 0) return -1; int m lights[0].size(); // dist[r][c][dir] 初始化为无穷大 // 使用 vector 初始化三维数组 vectorvectorvectorint dist(n, vectorvectorint(m, vectorint(4, INT_MAX))); // 优先队列 (小顶堆) priority_queueState, vectorState, greaterState pq; // 起点初始化可以假设从任意方向到达起点或者第一步无等待 // 我们将起点的4个方向都加入队列时间为0 for (int d 0; d 4; d) { dist[rowStart][colStart][d] 0; pq.push({0, rowStart, colStart, d}); } while (!pq.empty()) { State current pq.top(); pq.pop(); int t current.time; int r current.r; int c current.c; int inDir current.dir; // 剪枝如果当前取出的时间大于已记录的最短时间跳过 if (t dist[r][c][inDir]) { continue; } // 尝试向4个方向移动 for (int nextDir 0; nextDir 4; nextDir) { int nr r DR[nextDir]; int nc c DC[nextDir]; // 边界检查 if (nr 0 nr n nc 0 nc m) { int waitTime 0; // 规则起点交通灯不计入 if (r rowStart c colStart) { waitTime 0; } else { // 计算转向差值 // diff 1: 右转, 0: 直行, 3: 左转, 2: 掉头 int diff (nextDir - inDir 4) % 4; if (diff 1) { // 右转无需等待 waitTime 0; } else if (diff 2) { // 掉头通常不是最优解直接跳过 continue; } else { // 直行 (0) 或 左转 (3)需要等灯 int cycle lights[r][c]; if (cycle 0) { // 核心公式(T - (t % T)) % T waitTime (cycle - (t % cycle)) % cycle; } else { waitTime 0; } } } int newTime t waitTime timePerRoad; // 松弛操作 if (newTime dist[nr][nc][nextDir]) { dist[nr][nc][nextDir] newTime; pq.push({newTime, nr, nc, nextDir}); } } } } // 结果是终点4个方向中的最小值 int ans INT_MAX; for (int d 0; d 4; d) { ans min(ans, dist[rowEnd][colEnd][d]); } return (ans INT_MAX) ? -1 : ans; } int main() { // 优化 IO 速度 ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; if (!(cin n m)) return 0; vectorvectorint lights(n, vectorint(m)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin lights[i][j]; } } int timePerRoad; cin timePerRoad; int rowStart, colStart, rowEnd, colEnd; cin rowStart colStart; cin rowEnd colEnd; cout calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd) endl; return 0; }四、核心考点与避坑指南三维状态是关键很多考生只用了dist[r][c]导致无法区分“刚右转到达”和“刚直行到达”的状态。记住方向也是状态的一部分这是本题唯一的解题钥匙。等待时间公式陷阱正确公式(T - (t % T)) % T。错误写法T - (t % T)。当t是T的倍数时错误写法会得到T意味着要等一个完整周期而实际上应该是0刚好绿灯。外层% T至关重要。起点的特殊处理题目明确“起点交通灯不计入”。这意味着从起点出发的第一条边无论转向如何waitTime强制为 0。代码中通过if (r rowStart c colStart)实现了这一逻辑。C 优先队列细节priority_queue默认是大顶堆最大值在顶。求最短路需要小顶堆必须声明为priority_queueT, vectorT, greaterT并重载operator。使用tuple或struct均可struct可读性更好。掉头的处理在网格图中原地掉头diff 2通常意味着走回头路不可能构成最短路径。为了优化性能可以直接continue跳过。IO 优化在 C 机考中数据量较大时建议加上ios::sync_with_stdio(false); cin.tie(nullptr);以加速输入输出避免超时。五、结语这道题是带状态约束的最短路径问题的经典变种。它不仅仅考察 Dijkstra 算法的背诵更考察将实际业务规则交通规则抽象为图论模型的能力。掌握“坐标 方向”的状态扩展技巧你就能轻松解决此类问题甚至扩展到更复杂的场景如不同车型速度不同、携带物品限制等。C 凭借其高效的执行速度和丰富的 STL 容器是解决此类算法题的利器。希望这篇博文能助你在机考中旗开得胜如果觉得有帮助欢迎点赞、收藏、关注获取更多华为OD算法真题解析
【华为OD机考真题】智慧交通·路口最短时间问题 (C++)
发布时间：2026/5/20 7:44:23
一、题目假定街道是棋盘型的每格距离相等车辆通过每格街道需要时间均为 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. 为什么普通 Dijkstra 不够在标准最短路中dist[r][c]表示到达 (r,c) 的最短时间。但在本题中到达 (r,c) 的“未来代价”取决于你是从哪个方向来的。从北来车头朝南想去东→→左转→→需等灯。从西来车头朝东想去东→→直行→→需等灯。从北来车头朝南想去西→→右转→→不等灯。结论状态必须定义为(行, 列, 朝向)。朝向定义为到达该点时的车头方向即上一步的移动方向。方向编码0:上, 1:右, 2:下, 3:左。距离数组dist[n][m][4]。2. 算法流程初始化定义三维数组dist[n][m][4]初始化为INT_MAX。优先队列最小堆存入起点的 4 个可能状态(time0, r, c, dir)。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直行是 三、C 代码实现C 的priority_queue默认是大顶堆需要通过greater或自定义比较器改为小顶堆。以下代码使用了tuple和vector结构清晰效率极高。#include iostream #include vector #include queue #include tuple #include climits #include algorithm using namespace std; // 方向定义上(0), 右(1), 下(2), 左(3) // 对应坐标变化 (dr, dc) const int DR[] {-1, 0, 1, 0}; const int DC[] {0, 1, 0, -1}; // 状态结构体时间行列朝向 struct State { int time; int r; int c; int dir; // 重载 运算符用于优先队列的小顶堆排序 bool operator(const State other) const { return time other.time; } }; int calcTime(const vectorvectorint lights, int timePerRoad, int rowStart, int colStart, int rowEnd, int colEnd) { int n lights.size(); if (n 0) return -1; int m lights[0].size(); // dist[r][c][dir] 初始化为无穷大 // 使用 vector 初始化三维数组 vectorvectorvectorint dist(n, vectorvectorint(m, vectorint(4, INT_MAX))); // 优先队列 (小顶堆) priority_queueState, vectorState, greaterState pq; // 起点初始化可以假设从任意方向到达起点或者第一步无等待 // 我们将起点的4个方向都加入队列时间为0 for (int d 0; d 4; d) { dist[rowStart][colStart][d] 0; pq.push({0, rowStart, colStart, d}); } while (!pq.empty()) { State current pq.top(); pq.pop(); int t current.time; int r current.r; int c current.c; int inDir current.dir; // 剪枝如果当前取出的时间大于已记录的最短时间跳过 if (t dist[r][c][inDir]) { continue; } // 尝试向4个方向移动 for (int nextDir 0; nextDir 4; nextDir) { int nr r DR[nextDir]; int nc c DC[nextDir]; // 边界检查 if (nr 0 nr n nc 0 nc m) { int waitTime 0; // 规则起点交通灯不计入 if (r rowStart c colStart) { waitTime 0; } else { // 计算转向差值 // diff 1: 右转, 0: 直行, 3: 左转, 2: 掉头 int diff (nextDir - inDir 4) % 4; if (diff 1) { // 右转无需等待 waitTime 0; } else if (diff 2) { // 掉头通常不是最优解直接跳过 continue; } else { // 直行 (0) 或 左转 (3)需要等灯 int cycle lights[r][c]; if (cycle 0) { // 核心公式(T - (t % T)) % T waitTime (cycle - (t % cycle)) % cycle; } else { waitTime 0; } } } int newTime t waitTime timePerRoad; // 松弛操作 if (newTime dist[nr][nc][nextDir]) { dist[nr][nc][nextDir] newTime; pq.push({newTime, nr, nc, nextDir}); } } } } // 结果是终点4个方向中的最小值 int ans INT_MAX; for (int d 0; d 4; d) { ans min(ans, dist[rowEnd][colEnd][d]); } return (ans INT_MAX) ? -1 : ans; } int main() { // 优化 IO 速度 ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; if (!(cin n m)) return 0; vectorvectorint lights(n, vectorint(m)); for (int i 0; i n; i) { for (int j 0; j m; j) { cin lights[i][j]; } } int timePerRoad; cin timePerRoad; int rowStart, colStart, rowEnd, colEnd; cin rowStart colStart; cin rowEnd colEnd; cout calcTime(lights, timePerRoad, rowStart, colStart, rowEnd, colEnd) endl; return 0; }四、核心考点与避坑指南三维状态是关键很多考生只用了dist[r][c]导致无法区分“刚右转到达”和“刚直行到达”的状态。记住方向也是状态的一部分这是本题唯一的解题钥匙。等待时间公式陷阱正确公式(T - (t % T)) % T。错误写法T - (t % T)。当t是T的倍数时错误写法会得到T意味着要等一个完整周期而实际上应该是0刚好绿灯。外层% T至关重要。起点的特殊处理题目明确“起点交通灯不计入”。这意味着从起点出发的第一条边无论转向如何waitTime强制为 0。代码中通过if (r rowStart c colStart)实现了这一逻辑。C 优先队列细节priority_queue默认是大顶堆最大值在顶。求最短路需要小顶堆必须声明为priority_queueT, vectorT, greaterT并重载operator。使用tuple或struct均可struct可读性更好。掉头的处理在网格图中原地掉头diff 2通常意味着走回头路不可能构成最短路径。为了优化性能可以直接continue跳过。IO 优化在 C 机考中数据量较大时建议加上ios::sync_with_stdio(false); cin.tie(nullptr);以加速输入输出避免超时。五、结语这道题是带状态约束的最短路径问题的经典变种。它不仅仅考察 Dijkstra 算法的背诵更考察将实际业务规则交通规则抽象为图论模型的能力。掌握“坐标 方向”的状态扩展技巧你就能轻松解决此类问题甚至扩展到更复杂的场景如不同车型速度不同、携带物品限制等。C 凭借其高效的执行速度和丰富的 STL 容器是解决此类算法题的利器。希望这篇博文能助你在机考中旗开得胜如果觉得有帮助欢迎点赞、收藏、关注获取更多华为OD算法真题解析
