华为OD机试C卷：网格红绿灯最短路径算法详解与C++实现

1. 项目概述当最短路径遇上红绿灯如果你正在准备华为OD的机试尤其是C卷那么“网格红绿灯最短路径”这道题绝对是你绕不开的一座大山。这道题分值高达200分被归类在“最短路算法”的考点下足以说明它的分量。乍一看题目名字结合了“网格”、“红绿灯”和“最短路径”听起来像是把经典的图论问题放到了一个动态的、有时序约束的城市交通场景里。没错它的核心就是带时间约束的最短路径问题但它的难点在于这个“时间约束”不是简单的边权值而是一个周期性的、会动态变化的“通行时间窗口”。我当年准备机试时第一次看到这类题目也有点发怵。传统的Dijkstra算法处理的是静态图每条边的代价是固定的。但在这里你从A路口到B路口所花的时间取决于你到达A路口的时间点因为你需要等待红灯结束。这直接打破了传统最短路算法的“最优子结构”假设——你无法单纯根据当前已知的最短时间来判断后续路径是否最优。不过别担心一旦你理解了它的核心模型并掌握对经典算法的“改造”方法这道题就会从拦路虎变成你的得分利器。接下来我就结合C实现带你彻底拆解这道题。2. 核心思路拆解为什么Dijkstra需要“变形”面对“网格红绿灯最短路径”我们首先要摒弃寻找“最短物理距离”的惯性思维转而寻找“最短通行时间”。整个场景可以抽象为一个带权有向图或无向图但它的权值是随时间变化的函数。2.1 问题建模与关键挑战图的构建节点Vertex每个网格的十字路口。对于一个m x n的网格通常有m * n个节点。边Edge连接相邻路口上下左右的道路。每条边有一个固定的通行耗时比如t秒。红绿灯约束每个节点路口都有一个红绿灯周期。例如周期为period秒其中红灯red秒绿灯green秒period red green。当你到达一个节点时你需要根据当前时刻判断是否需要等待。核心挑战到达时间决定等待时间。假设你在T时刻到达某个路口该路口的红绿灯周期是period红灯时段为[0, red)绿灯时段为[red, period)然后不断循环。计算T在周期内的相位phase T % period。如果phase red说明当前是红灯你需要等待(red - phase)秒。如果phase red说明当前是绿灯你可以立即通行等待0秒。因此从到达路口到离开路口总耗时 等待时间 穿越路口的耗时通常为0或一个固定小值 下一条道路的通行耗时。这就导致了一个关键问题从节点A到节点B的“代价”不是一个固定值而是取决于到达A的时间。这违反了标准Dijkstra算法中“边权非负且固定”的基本假设。我们不能在初始化时就把边权确定下来。2.2 算法选型时间扩展图 vs. 修改松弛策略解决这类“时变图”最短路径问题主要有两种主流思路方案一构建时间扩展图Time-Expanded Graph这是最直观也最“暴力”的方法。我们把时间也作为一个维度。假设总时间可能上限为T_max我们为每个原始节点在每个时间点0, 1, 2, ..., T_max都创建一个副本节点(node_id, time)。然后根据红绿灯规则在这些时空节点之间连边。优点模型清晰将动态图转化为静态图可以直接套用标准最短路算法。致命缺点T_max可能很大导致节点数量爆炸O(N * T_max)内存和时间开销都无法承受。在竞赛或机试场景下这通常不是可行方案。方案二修改Dijkstra算法的松弛Relax操作这是更优雅和高效的做法。我们依然使用Dijkstra算法的框架使用优先队列最小堆来维护“当前已知从起点到各节点的最短时间”。但是在尝试用节点u去更新其邻居v时我们不能直接用dist[u] weight(u, v)去比较dist[v]。我们计算从u出发的实际时间arrival_at_u dist[u]。根据arrival_at_u和u节点的红绿灯规则计算在u节点的等待时间wait_time。那么从u到v的实际耗时为cost wait_time cross_time(u) road_time(u, v)。其中cross_time(u)是穿越路口u的耗时常为0或1road_time(u, v)是道路通行耗时。则到达v的新时间为new_time_to_v arrival_at_u cost。如果new_time_to_v dist[v]则更新dist[v]并将(new_time_to_v, v)入堆。为什么Dijkstra依然有效虽然边权可变但只要等待时间函数是非负的那么从起点到任意节点的“最短到达时间”在算法过程中仍然是单调不减地被发现和确定的。修改后的松弛操作保证了我们每次从堆中取出的节点其当前dist值就是它的最终最短时间。这是解决本题最核心的洞见。注意这里有一个非常重要的细节即“穿越路口”的耗时cross_time。有些题目设定中等待红灯发生在进入路口之前绿灯亮起后“瞬间”穿越路口而另一些设定中穿越路口本身也需要1个单位时间。务必仔细阅读题目输入输出说明这个细节会直接影响wait_time的计算逻辑。在本文的后续实现中我们采用“等待后瞬间穿越”的模型即cross_time 0。3. 数据结构设计与输入处理在动手写核心算法之前良好的数据结构设计能让代码清晰且不易出错。我们假设题目输入格式如下具体格式需以真题为准这里是常见格式 第一行两个整数m,n表示网格的行数和列数。 第二行四个整数start_x,start_y,end_x,end_y表示起点和终点的坐标从0开始或从1开始需确认。 随后m行每行n个字符串或整数描述每个路口的红绿灯周期。例如10 5表示周期period10红灯red5绿灯green5。 随后可能还有m行或类似描述水平道路的通行耗时以及m-1行描述垂直道路的通行耗时。有时为了简化所有道路耗时相同比如都是1。为了通用性我们设计以下结构#include iostream #include vector #include queue #include climits using namespace std; // 定义方向数组上、下、左、右 const int dirs[4][2] {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; struct TrafficLight { int period; // 红绿灯总周期 int red; // 红灯时长 // 绿灯时长 period - red可以不用显式存储 TrafficLight(int p0, int r0) : period(p), red(r) {} }; struct Node { int time; // 到达该节点的当前最短时间 int x, y; // 节点的坐标 // 重载运算符用于优先队列最小堆 bool operator(const Node other) const { return time other.time; // 注意优先队列默认是最大堆我们需要最小堆所以用 } };输入处理逻辑我们需要将二维网格坐标映射到一维索引或者直接使用二维坐标。使用二维vector存储每个节点的红绿灯信息、最短到达时间以及道路耗时如果道路耗时因方向而异可能需要更复杂的数据结构。int main() { int m, n; cin m n; int startX, startY, endX, endY; cin startX startY endX endY; // 调整坐标如果输入是1-indexed则转为0-indexed // startX--; startY--; endX--; endY--; vectorvectorTrafficLight lights(m, vectorTrafficLight(n)); vectorvectorint horizontalTime(m, vectorint(n-1, 1)); // 水平道路耗时默认1 vectorvectorint verticalTime(m-1, vectorint(n, 1)); // 垂直道路耗时默认1 // 读取红绿灯信息 for (int i 0; i m; i) { for (int j 0; j n; j) { int period, red; cin period red; lights[i][j] TrafficLight(period, red); } } // 如果题目提供了道路耗时矩阵则在这里读取覆盖默认值 // readRoadTimes(horizontalTime, verticalTime); // 调用核心算法函数 int result shortestPathWithTrafficLight(m, n, startX, startY, endX, endY, lights, horizontalTime, verticalTime); cout result endl; return 0; }4. 核心算法实现改造Dijkstra这是整个解决方案的心脏。我们将实现一个函数接收所有参数返回从起点到终点的最短时间。int shortestPathWithTrafficLight(int m, int n, int startX, int startY, int endX, int endY, const vectorvectorTrafficLight lights, const vectorvectorint horizontalTime, const vectorvectorint verticalTime) { // 初始化距离数组所有节点时间为无穷大 vectorvectorint dist(m, vectorint(n, INT_MAX)); dist[startX][startY] 0; // 优先队列最小堆存储 (到达时间, x, y) priority_queueNode, vectorNode, greaterNode pq; pq.push({0, startX, startY}); while (!pq.empty()) { Node current pq.top(); pq.pop(); int curTime current.time; int x current.x; int y current.y; // 经典的Dijkstra优化如果弹出的节点时间大于当前记录的距离说明是旧数据跳过 if (curTime dist[x][y]) { continue; } // 如果已经到达终点可以提前结束Dijkstra特性保证第一次弹出终点时即为最短时间 if (x endX y endY) { return curTime; } // 遍历四个方向 for (int d 0; d 4; d) { int nx x dirs[d][0]; int ny y dirs[d][1]; // 检查新坐标是否越界 if (nx 0 || nx m || ny 0 || ny n) { continue; } // 计算从当前节点(x,y)移动到邻居节点(nx,ny)所需的总时间 int roadCost; // 判断是水平移动还是垂直移动以获取道路耗时 if (dirs[d][0] 0) { // 水平移动左或右 // 道路位于 y 和 ny 之间取最小值作为索引 int minY min(y, ny); roadCost horizontalTime[x][minY]; } else { // 垂直移动上或下 int minX min(x, nx); roadCost verticalTime[minX][y]; } // 关键步骤计算在路口(x,y)的等待时间 const TrafficLight tl lights[x][y]; int waitTime 0; if (tl.period 0) { // 如果有红绿灯 int phase curTime % tl.period; if (phase tl.red) { waitTime tl.red - phase; } // 否则 phase tl.red等待时间为0 } // 注意这里假设穿越路口本身不需要时间cross_time 0 // 如果需要则 totalCost waitTime cross_time roadCost; int totalCost waitTime roadCost; int newTime curTime totalCost; // 如果找到更短的路径更新并加入队列 if (newTime dist[nx][ny]) { dist[nx][ny] newTime; pq.push({newTime, nx, ny}); } } } // 如果队列为空仍未到达终点说明终点不可达根据题意通常不会 return -1; // 或返回 dist[endX][endY] (此时为INT_MAX) }代码精讲数据结构使用dist二维数组记录最短时间优先队列pq进行贪心扩展。去重优化if (curTime dist[x][y]) continue;这行至关重要。因为同一个节点可能被多次加入堆随着更短路径的发现这个检查可以丢弃过时的、非最优的堆顶元素提升效率。等待时间计算phase curTime % period得到当前时间在红绿灯周期中的位置。如果落在红灯区间[0, red)内则等待red - phase秒。道路耗时获取通过判断移动方向从对应的horizontalTime或verticalTime矩阵中读取边权。这里假设输入的道路耗时矩阵已经正确初始化。提前终止当终点第一次从堆中弹出时根据Dijkstra算法的性质其time值就是全局最短时间可以直接返回无需遍历完所有节点。5. 边界条件与常见陷阱即使算法逻辑正确忽略边界条件也会导致功亏一篑。下面是我在调试和实战中总结的几个关键陷阱5.1 起点和终点的红绿灯处理题目通常要求计算从起点出发到终点到达的时间。这里容易混淆两个点起点是否需要等红绿灯绝大多数情况下起点不需要等待。因为你是从起点开始出发时间是0除非题目特别说明“在起点也要遵守交通灯”否则应假设起点立即通行。我们的代码中第一次从起点扩展邻居时curTime0会计算起点的等待时间。如果起点红灯会导致不必要的等待。解决方案在起点第一次扩展时特殊处理将起点的等待时间强制设为0。终点是否需要考虑红绿灯不需要。当你到达终点坐标时旅程已经结束无需再考虑终点的红绿灯状态。我们的算法在判断if (x endX y endY)时直接返回时间正是符合这一逻辑。修正后的等待时间计算片段// 计算在路口(x,y)的等待时间 int waitTime 0; // 如果是起点且当前时间为0即第一次出发则不等灯 if (!(x startX y startY curTime 0)) { const TrafficLight tl lights[x][y]; if (tl.period 0) { int phase curTime % tl.period; if (phase tl.red) { waitTime tl.red - phase; } } }5.2 周期为0或红灯为0的特殊情况题目中某些路口可能没有红绿灯或者始终是绿灯。这通常通过period0或red0来表示。如果period 0可以视为没有红绿灯等待时间始终为0。如果red 0说明一直是绿灯等待时间也始终为0。 在计算phase前必须检查period是否大于0否则会出现除零错误。上面的代码通过if (tl.period 0)进行了保护。5.3 大整数与溢出问题时间值在算法运行中可能不断累加。如果网格很大、周期很长、道路耗时不小最终的最短时间有可能超过int的范围约21亿。虽然机试环境下的数据通常不会这么极端但养成好习惯很重要。可以使用long long类型来存储dist和计算过程中的时间值。vectorvectorlong long dist(m, vectorlong long(n, LLONG_MAX)); priority_queuepairlong long, pairint, int, vector..., greater... pq;5.4 道路耗时矩阵的索引在获取horizontalTime和verticalTime时索引的计算要小心。例如对于节点(x, y)和其右边的节点(x, y1)连接它们的水平道路耗时应该存储在horizontalTime[x][y]假设矩阵定义中horizontalTime[i][j]表示第i行第j条垂直道路右侧的水平道路即连接(i,j)和(i, j1)的道路。务必根据题目示例或说明确认索引规则最好自己画一个3x3的网格标出所有道路和索引验证代码逻辑。6. 性能优化与实战技巧在机试的紧张环境中一个高效的实现不仅能保证通过还能为你节省宝贵时间。6.1 使用更高效的距离更新判断在将新节点加入优先队列前我们进行了if (newTime dist[nx][ny])的判断。这是正确的。有些初学者会想“我先更新dist再入堆”逻辑一样。但保持“先判断再更新和入堆”的顺序更清晰。6.2 避免不必要的节点扩展我们的代码中有一个优化if (curTime dist[x][y]) continue;。这能过滤掉堆中的过期数据。另一个常见的优化是当从堆中取出终点时直接返回。Dijkstra算法保证第一次访问终点时就是最短路径这个优化在终点离起点较近时效果明显。6.3 输入输出加速对于C如果输入数据量较大比如网格达到100x100数据量上万关闭C标准流与C标准流的同步可以显著提升读取速度。ios::sync_with_stdio(false); cin.tie(nullptr);在机试平台上通常不需要但如果你在自己本地测试大数据时感觉慢可以加上。6.4 调试与测试用例构造自己构造测试用例是调试的关键。从最简单的开始1x2网格起点(0,0)终点(0,1)无红绿灯道路耗时1。结果应为1。1x2网格起点(0,0)终点(0,1)路口(0,0)红绿灯周期5红灯5常红。结果应为到达(0,0)时间0红灯需等5秒总耗时516。2x2网格测试绕路是否比等红灯更快。例如从(0,0)到(0,1)(0,0)路口红灯很长但绕道(1,0)-(1,1)-(0,1)可能更快。边界测试period0,red0, 起点终点相同结果应为0。将这些用例写成代码用assert验证能快速定位逻辑错误。7. 完整代码整合与示例运行将上述所有部分整合并添加详细的注释就得到了一份健壮的解决方案。以下是完整的代码框架#include iostream #include vector #include queue #include climits using namespace std; struct TrafficLight { int period, red; }; // 方向上、下、左、右 const int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; int shortestPath(int m, int n, int sx, int sy, int ex, int ey, const vectorvectorTrafficLight light, const vectorvectorint hTime, const vectorvectorint vTime) { vectorvectorlong long dist(m, vectorlong long(n, LLONG_MAX)); dist[sx][sy] 0; // 优先队列元素pair时间, pairx, y using P pairlong long, pairint, int; priority_queueP, vectorP, greaterP pq; pq.push({0, {sx, sy}}); while (!pq.empty()) { auto [curTime, pos] pq.top(); pq.pop(); int x pos.first, y pos.second; if (curTime dist[x][y]) continue; if (x ex y ey) return (int)curTime; // 题目要求返回int for (int d 0; d 4; d) { int nx x dirs[d][0], ny y dirs[d][1]; if (nx 0 || nx m || ny 0 || ny n) continue; // 获取道路耗时 int roadCost; if (dirs[d][0] 0) { // 水平 int minY min(y, ny); roadCost hTime[x][minY]; } else { // 垂直 int minX min(x, nx); roadCost vTime[minX][y]; } // 计算等待时间起点出发不等灯 long long waitTime 0; if (!(x sx y sy curTime 0)) { const TrafficLight tl light[x][y]; if (tl.period 0) { int phase (int)(curTime % tl.period); if (phase tl.red) waitTime tl.red - phase; } } long long newTime curTime waitTime roadCost; if (newTime dist[nx][ny]) { dist[nx][ny] newTime; pq.push({newTime, {nx, ny}}); } } } return -1; // 不可达 } int main() { // 关闭同步加速IO按需使用 // ios::sync_with_stdio(false); cin.tie(nullptr); int m, n; cin m n; int sx, sy, ex, ey; cin sx sy ex ey; // 如果输入是1-indexed在此处转换为0-indexed // sx--; sy--; ex--; ey--; vectorvectorTrafficLight light(m, vectorTrafficLight(n)); for (int i 0; i m; i) for (int j 0; j n; j) cin light[i][j].period light[i][j].red; // 假设所有道路耗时为1根据题目要求修改 vectorvectorint hTime(m, vectorint(n-1, 1)); vectorvectorint vTime(m-1, vectorint(n, 1)); // 如果题目提供了道路耗时在此处读取并填充 hTime, vTime int ans shortestPath(m, n, sx, sy, ex, ey, light, hTime, vTime); cout ans endl; return 0; }示例运行假设输入为2 2 0 0 1 1 5 3 5 3 5 3 5 3表示一个2x2网格起点(0,0)终点(1,1)。每个路口的红绿灯周期都是5红灯都是3即绿灯为2。所有道路耗时默认为1。手动推导从(0,0)出发时间0。路口(0,0)红灯phase03等待3秒然后走右边到(0,1)耗时1秒。到达(0,1)时间为4。在(0,1)时间4。路口(0,1) phase4%5443是绿灯不等灯。走下边到(1,1)耗时1秒。到达(1,1)时间为5。另一条路从(0,0)先走下边到(1,0)同理在(0,0)等3秒耗时1秒到达(1,0)时间为4。在(1,0)等灯phase4%54绿灯再走到(1,1)总时间也是5。 程序应输出5。8. 总结与扩展思考通过上面的详细拆解我们可以看到“网格红绿灯最短路径”的本质是一个时间依赖的最短路径问题。解决它的核心在于理解传统Dijkstra算法“松弛”操作的内涵并针对“边权是到达时间的函数”这一特点对松弛过程进行定制化修改。这道题很好地考察了以下几个能力问题抽象与建模能力能否将现实的红绿灯规则转化为可计算的等待时间函数。经典算法的灵活应用能力不死记硬背Dijkstra模板而是理解其原理并能进行改造。边界情况处理能力起点、周期为0、坐标转换等细节。代码实现与调试能力在有限时间内写出结构清晰、逻辑正确的代码。扩展思考如果红绿灯周期不是从0时刻开始而是有一个初始偏移量怎么办比如红灯时段是[offset, offsetred)。这只需要修改相位计算phase (curTime - offset) % period并注意对负数取模的处理在C中%可能产生负数需要调整phase ((curTime - offset) % period period) % period。如果道路是双向的但不同方向有不同的耗时或红绿灯规则这就需要将图构建为有向图每个方向作为一条独立的边来处理。是否存在比修改Dijkstra更优的算法对于这种边权是到达时间分段常数函数的问题修改Dijkstra的A*算法是已知的高效方法。但在华为OD机试的约束下掌握修改Dijkstra的方法已经完全足够。最后给正在备考的同学一个建议理解原理比背诵代码更重要。尝试在不看代码的情况下自己从头推导一遍等待时间的计算画一个小网格模拟算法过程。当你真正搞懂为什么这样做是对的遇到任何变体题目都能游刃有余。这道200分的题希望你能稳稳拿下。