C语言迪杰特斯拉算法：精准求解矩形迷宫最短路径并输出节点位置

```c #include <stdio.h> #include <stdlib.h> // 定义一个结构体来表示矩阵中的点 typedef struct Point { int x; int y; } Point; // 定义一个结构体来表示队列中的节点 typedef struct QueueNode { Point point; int distance; struct QueueNode *next; } QueueNode; // 初始化队列 QueueNode *initQueue() { return NULL; } // 入队操作 void enqueue(QueueNode head, QueueNode tail, Point point, int distance) { QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode)); newNode->point = point; newNode->distance = distance; newNode->next = NULL; if (*head == NULL) { *head = newNode; } else { (*tail)->next = newNode; } *tail = newNode; } // 出队操作 QueueNode *dequeue(QueueNode head, QueueNode tail) { if (*head == NULL) { return NULL; } QueueNode *temp = *head; *head = (*head)->next; if (*head == NULL) { *tail = NULL; } return temp; } // 判断一个点是否合法 int is_valid(int rows, int cols, int x, int y) { return x >= 0 && x < rows && y >= 0 && y < cols; } // 迪杰特斯拉算法 void dijkstra(int rows, int cols, int maze[][cols], Point start, Point end) { int distances[rows][cols]; int visited[rows][cols]; QueueNode *head = initQueue(); QueueNode *tail = NULL; // 初始化距离和访问数组 for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { distances[i][j] = INT_MAX; visited[i][j] = 0; } } distances[start.x][start.y] = 0; enqueue(&head, &tail, start, 0); while (head!= NULL) { QueueNode *current = dequeue(&head, &tail); Point p = current->point; visited[p.x][p.y] = 1; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; for (int i = 0; i < 4; i++) { int newX = p.x + dx[i]; int newY = p.y + dy[i]; if (is_valid(rows, cols, newX, newY) && maze[newX][newY]!= 0 &&!visited[newX][newY]) { int newDistance = distances[p.x][p.y] + 1; if (newDistance < distances[newX][newY]) { distances[newX][newY] = newDistance; Point newPoint = {newX, newY}; enqueue(&head, &tail, newPoint, newDistance); } } } } // 输出最短路径 if (distances[end.x][end.y]!= INT_MAX) { Point current = end; while (current.x!= start.x || current.y!= start.y) { printf("%d %d\n", current.x, current.y); int minDistance = INT_MAX; Point minPoint; int dx[] = {-1, 1, 0, 0}; int dy[] = {0, 0, -1, 1}; for (int i = 0; i < 4; i++) { int newX = current.x + dx[i]; int newY = current.y + dy[i]; if (is_valid(rows, cols, newX, newY) && distances[newX][newY] < minDistance) { minDistance = distances[newX][newY]; minPoint = {newX, newY}; } } current = minPoint; } printf("%d %d\n", start.x, start.y); } else { printf("No path found!\n"); } } int main() { int rows, cols; scanf("%d %d", &rows, &cols); int maze[rows][cols]; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { scanf("%d", &maze[i][j]); } } Point start = {-1, -1}; Point end = {-1, -1}; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (maze[i][j] == 3) { start.x = i; start.y = j; } else if (maze[i][j] == 4) { end.x = i; end.y = j; } } } dijkstra(rows, cols, maze, start, end); return 0; } ``` 以下是 3 点额外需要注意的逻辑点： 1. 输入的矩阵数据要确保准确无误，否则可能导致算法出错。 2. 对于边界情况的处理要仔细，比如在遍历相邻点时，要确保不会越界。 3. 输出的路径顺序要按照从入口到出口的顺序，并且要包含入口和出口点。 ######[AI写代码神器 | 1362点数解答 | 2024-12-16 22:29:42]