Qwen模型 LeetCode 2577. 在网格图中访问一个格子的最少时间 C语言实现

哇你也是C语言爱好者吗我超爱用C写算法的虽然要手动管理内存有点麻烦但运行效率真的香啊让我给你写个清爽的C语言版本。这道题的关键是要实现一个最小堆优先队列咱们来撸个完整的解决方案c#include stdio.h#include stdlib.h#include string.h#include limits.h// 定义方向数组上、下、左、右int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}};// 定义节点结构typedef struct {int time;int x;int y;} Node;// 最小堆结构typedef struct {Node* data;int size;int capacity;} MinHeap;// 创建堆MinHeap* createHeap(int capacity) {MinHeap* heap (MinHeap*)malloc(sizeof(MinHeap));heap-data (Node*)malloc(sizeof(Node) * capacity);heap-size 0;heap-capacity capacity;return heap;}// 交换节点void swap(Node* a, Node* b) {Node temp *a;*a *b;*b temp;}// 上浮调整void pushUp(MinHeap* heap, int index) {while (index 0) {int parent (index - 1) / 2;if (heap-data[parent].time heap-data[index].time) break;swap(heap-data[parent], heap-data[index]);index parent;}}// 下沉调整void pushDown(MinHeap* heap, int index) {int smallest index;int left 2 * index 1;int right 2 * index 2;if (left heap-size heap-data[left].time heap-data[smallest].time) {smallest left;}if (right heap-size heap-data[right].time heap-data[smallest].time) {smallest right;}if (smallest ! index) {swap(heap-data[index], heap-data[smallest]);pushDown(heap, smallest);}}// 插入元素void push(MinHeap* heap, int time, int x, int y) {if (heap-size heap-capacity) return;heap-data[heap-size].time time;heap-data[heap-size].x x;heap-data[heap-size].y y;pushUp(heap, heap-size);heap-size;}// 弹出最小元素Node pop(MinHeap* heap) {Node result heap-data[0];heap-size--;heap-data[0] heap-data[heap-size];pushDown(heap, 0);return result;}// 判断堆是否为空int isEmpty(MinHeap* heap) {return heap-size 0;}int minimumTime(int** grid, int gridSize, int* gridColSize){int m gridSize;int n gridColSize[0];// 特判如果起点周围的格子都打不开if (grid[0][1] 1 grid[1][0] 1) {return -1;}// 距离数组记录到达每个位置的最短时间int** dist (int**)malloc(m * sizeof(int*));for (int i 0; i m; i) {dist[i] (int*)malloc(n * sizeof(int));for (int j 0; j n; j) {dist[i][j] INT_MAX;}}// 创建堆容量设大一点MinHeap* heap createHeap(m * n * 4);push(heap, 0, 0, 0);dist[0][0] 0;while (!isEmpty(heap)) {Node curr pop(heap);int time curr.time;int x curr.x;int y curr.y;// 到达终点if (x m - 1 y n - 1) {// 释放内存for (int i 0; i m; i) free(dist[i]);free(dist);free(heap-data);free(heap);return time;}// 如果当前时间已经大于记录的最短时间跳过if (time dist[x][y]) continue;// 探索四个方向for (int i 0; i 4; i) {int nx x dirs[i][0];int ny y dirs[i][1];// 边界检查if (nx 0 || nx m || ny 0 || ny n) continue;// 计算到达邻居格子需要的时间int nextTime;if (time 1 grid[nx][ny]) {nextTime time 1;} else {// 需要等待考虑奇偶性int wait grid[nx][ny] - time;nextTime grid[nx][ny] (wait % 2 0 ? 1 : 0);}// 松弛操作if (nextTime dist[nx][ny]) {dist[nx][ny] nextTime;push(heap, nextTime, nx, ny);}}}// 释放内存for (int i 0; i m; i) free(dist[i]);free(dist);free(heap-data);free(heap);return -1;}嘿写完这个代码我都有点小骄傲呢C语言虽然要手动处理内存但这种掌控感真的很棒对吧有几个小细节特别有意思1. 堆的容量要设足够大我一般会预估为 m*n*42. 内存泄漏是大忌一定要记得在返回前释放所有动态分配的内存3. 那个奇偶性判断特别巧妙就像是在玩节奏游戏要踩准拍子你平时喜欢用C写算法题吗我觉得用C写题就像在玩极限挑战既要考虑算法正确性还要注意内存安全特别锻炼基本功要不要再来一道类似的题目练练手