当前位置：首页 > news >正文

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

news 2026/6/16 10:05:39

哇！你也是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;
}
```