【华为OD机考真题】智慧交通·路口最短时间问题 (C语言)

一、题目假定街道是棋盘型的每格距离相等车辆通过每格街道需要时间均为 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. 核心建模为什么需要三维状态在普通最短路中dist[r][c]足以表示最短时间。但在本题中到达 (r,c) 的代价取决于“车头朝向”。从北向南到达车头朝南若下一步向东 →→左转→→需等灯。从西向东到达车头朝东若下一步向东 →→直行→→需等灯。从北向南到达车头朝南若下一步向西 →→右转→→不等灯。因此状态必须定义为(行, 列, 朝向)。朝向编码0:上, 1:右, 2:下, 3:左。距离数组dist[n][m][4]。2. 转向判断逻辑设当前朝向为in_dir下一步朝向为next_dir相对角度diff (next_dir - in_dir 4) % 4判定规则diff 1右转→→ 等待 0。diff 2掉头→→ 跳过非最优。diff 0或3直行/左转→→ 计算等待时间。3. C语言实现难点与对策难点1没有优先队列。对策手写一个基于数组的最小堆Min-Heap支持push和pop操作。难点2没有动态三维数组。对策根据题目通常的数据范围如 N,M≤50 或 100 直接定义足够大的静态三维数组int dist[100][100][4]避免复杂的内存分配错误。三、C语言代码实现本代码完全遵循 C99 标准包含完整的最小堆实现和主逻辑可直接在本地编译器或机考环境中运行。#include stdio.h #include stdlib.h #include string.h #include limits.h // 定义最大网格尺寸可根据题目实际约束调整 (例如 100x100) #define MAX_N 100 #define MAX_M 100 #define INF INT_MAX // 方向定义0:上, 1:右, 2:下, 3:左 const int DR[] {-1, 0, 1, 0}; const int DC[] {0, 1, 0, -1}; // 状态结构体 typedef struct { int time; int r; int c; int dir; } State; // 最小堆结构体 typedef struct { State *data; int size; int capacity; } MinHeap; // 堆初始化 MinHeap* heap_create(int capacity) { MinHeap *heap (MinHeap*)malloc(sizeof(MinHeap)); heap-data (State*)malloc(sizeof(State) * capacity); heap-size 0; heap-capacity capacity; return heap; } // 堆交换 void heap_swap(MinHeap *heap, int i, int j) { State temp heap-data[i]; heap-data[i] heap-data[j]; heap-data[j] temp; } // 上浮操作 void heap_push(MinHeap *heap, State val) { if (heap-size heap-capacity) { // 简单扩容策略实际机考中可预设足够大的容量 heap-capacity * 2; heap-data (State*)realloc(heap-data, sizeof(State) * heap-capacity); } int i heap-size; heap-data[i] val; // 上浮 while (i 0) { int parent (i - 1) / 2; if (heap-data[parent].time heap-data[i].time) { heap_swap(heap, parent, i); i parent; } else { break; } } } // 下沉操作 void heap_pop(MinHeap *heap) { if (heap-size 0) return; heap-data[0] heap-data[--heap-size]; int i 0; while (2 * i 1 heap-size) { int left 2 * i 1; int right 2 * i 2; int smallest left; if (right heap-size heap-data[right].time heap-data[left].time) { smallest right; } if (heap-data[i].time heap-data[smallest].time) { heap_swap(heap, i, smallest); i smallest; } else { break; } } } // 获取堆顶元素 State heap_top(MinHeap *heap) { return heap-data[0]; } // 判断堆空 int heap_empty(MinHeap *heap) { return heap-size 0; } // 释放堆 void heap_free(MinHeap *heap) { free(heap-data); free(heap); } int solve() { int n, m; if (scanf(%d %d, n, m) ! 2) return 0; // 使用静态数组存储 lights避免动态分配失败风险 static int lights[MAX_N][MAX_M]; for (int i 0; i n; i) { for (int j 0; j m; j) { scanf(%d, lights[i][j]); } } int timePerRoad; scanf(%d, timePerRoad); int rStart, cStart, rEnd, cEnd; scanf(%d %d, rStart, cStart); scanf(%d %d, rEnd, cEnd); // 距离数组 dist[r][c][dir] // 初始化为 INF static int dist[MAX_N][MAX_M][4]; for (int i 0; i n; i) { for (int j 0; j m; j) { for (int k 0; k 4; k) { dist[i][j][k] INF; } } } // 创建最小堆预估容量 (n*m*4)*2 MinHeap *pq heap_create(n * m * 16); // 初始化起点4个方向入队时间为0 for (int d 0; d 4; d) { dist[rStart][cStart][d] 0; State startState {0, rStart, cStart, d}; heap_push(pq, startState); } while (!heap_empty(pq)) { State cur heap_top(pq); heap_pop(pq); int t cur.time; int r cur.r; int c cur.c; int inDir cur.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 rStart c cStart) { waitTime 0; } else { // 计算转向差值 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; State nextState {newTime, nr, nc, nextDir}; heap_push(pq, nextState); } } } } // 结果是终点4个方向中的最小值 int ans INF; for (int d 0; d 4; d) { if (dist[rEnd][cEnd][d] ans) { ans dist[rEnd][cEnd][d]; } } heap_free(pq); if (ans INF) return -1; return ans; } int main() { int result solve(); printf(%d\n, result); return 0; }四、关键点深度解析1. 手写最小堆Min-HeapC 语言标准库stdlib.h只有qsort没有优先队列。数据结构使用数组data存储State结构体。上浮Push新元素放在末尾若比父节点小则交换直到满足堆性质。下沉Pop将末尾元素移到根节点若比子节点大则与较小的子节点交换直到满足堆性质。复杂度插入和删除均为 O(log⁡K)其中 KK 是堆中元素个数。2. 等待时间公式的严谨性waitTime (cycle - (t % cycle)) % cycle;场景A t10,cycle5 。10%50 。 (5−0)%50 。正确刚好绿灯。场景B t11,cycle5 。11%511 。(5−1)%54 。正确需等4秒。易错点如果写成cycle - (t % cycle)场景A会得到5秒导致错误。3. 静态数组 vs 动态分配在机考环境中为了代码的稳健性和简洁性定义了MAX_N和MAX_M通常设为100或200覆盖绝大多数题目数据范围。使用static int dist[MAX_N][MAX_M][4]直接在栈/数据段分配内存避免了malloc三层指针的繁琐和潜在泄漏风险。如果题目明确 N,M 非常大如 1000 则需改用malloc动态分配二维/三维数组。4. 起点的特殊处理代码中if (r rStart c cStart)确保了第一步永远不需要等待。这是题目隐含的“车辆已在起点准备好”的逻辑。 五、总结与建议这道题是考察图论建模能力与C语言基本功的完美结合。建模将“朝向”纳入状态把物理规则转化为图的边权。实现在无 STL 辅助的情况下手写数据结构解决复杂问题。给 C 语言考生的建议熟记手写堆的模板这是解决最短路、TopK 问题的利器。注意整数溢出虽然本题时间累加一般不会超过int范围但在其他题目中建议使用long long。调试时可以打印dist数组的部分值观察状态更新是否符合预期。掌握这套思路无论是华为 OD 还是其他大厂笔试中的“带约束最短路”问题都能迎刃而解