迷宫求最短路径c语言代码

以下是使用广度优先搜索算法求解迷宫最短路径的 C 语言代码：

#include <stdio.h>
#include <stdlib.h>

#define ROW 10 // 迷宫行数
#define COL 10 // 迷宫列数

// 定义结构体表示坐标
typedef struct {
    int x; // 行坐标
    int y; // 列坐标
} Coordinate;

// 定义队列结构体
typedef struct {
    Coordinate data[ROW * COL]; // 队列数据
    int front; // 队首指针
    int rear; // 队尾指针
} Queue;

// 初始化队列
void initQueue(Queue *q) {
    q->front = q->rear = 0;
}

// 判断队列是否为空
int isQueueEmpty(Queue *q) {
    return q->front == q->rear;
}

// 入队操作
void enqueue(Queue *q, Coordinate c) {
    q->data[q->rear++] = c;
}

// 出队操作
Coordinate dequeue(Queue *q) {
    return q->data[q->front++];
}

// 判断坐标是否越界
int isOutOfBound(Coordinate c) {
    return c.x < 0 || c.y < 0 || c.x >= ROW || c.y >= COL;
}

// 判断坐标是否为墙
int isWall(int maze[ROW][COL], Coordinate c) {
    return maze[c.x][c.y] == 1;
}

// 判断坐标是否已经访问过
int isVisited(int visited[ROW][COL], Coordinate c) {
    return visited[c.x][c.y] == 1;
}

// 标记坐标已经访问过
void markVisited(int visited[ROW][COL], Coordinate c) {
    visited[c.x][c.y] = 1;
}

// 判断是否为出口
int isExit(Coordinate c, Coordinate exit) {
    return c.x == exit.x && c.y == exit.y;
}

// 广度优先搜索求解最短路径
int bfs(int maze[ROW][COL], Coordinate start, Coordinate exit) {
    int visited[ROW][COL] = {0}; // 标记已经访问过的坐标
    int distance[ROW][COL] = {0}; // 记录起点到每个坐标的距离
    Queue q; // 定义队列
    initQueue(&q); // 初始化队列
    enqueue(&q, start); // 入队起点
    markVisited(visited, start); // 标记起点已经访问过
    while (!isQueueEmpty(&q)) {
        Coordinate current = dequeue(&q); // 取出队首元素
        if (isExit(current, exit)) { // 到达出口
            return distance[current.x][current.y]; // 返回最短路径长度
        }
        // 枚举当前坐标的四个方向
        Coordinate dirs[4] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < 4; i++) {
            Coordinate next = {current.x + dirs[i].x, current.y + dirs[i].y};
            if (isOutOfBound(next) || isWall(maze, next) || isVisited(visited, next)) {
                continue; // 如果下一个坐标越界、是墙或已经访问过，继续枚举下一个方向
            }
            enqueue(&q, next); // 将下一个坐标入队
            markVisited(visited, next); // 标记下一个坐标已经访问过
            distance[next.x][next.y] = distance[current.x][current.y] + 1; // 更新下一个坐标的距离
        }
    }
    return -1; // 没有找到最短路径
}

int main() {
    int maze[ROW][COL] = {
        {0, 1, 0, 0, 0, 0, 0, 1, 0, 0},
        {0, 1, 0, 1, 1, 1, 0, 1, 0, 1},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {1, 0, 1, 1, 1, 1, 1, 1, 1, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
        {0, 1, 1, 1, 1, 1, 1, 1, 1, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 1, 1, 1, 1, 1, 1, 1, 1, 0}
    };
    Coordinate start = {0, 0}; // 起点坐标
    Coordinate exit = {9, 9}; // 出口坐标
    int distance = bfs(maze, start, exit); // 求解最短路径长度
    if (distance == -1) {
        printf("迷宫没有出口！\n");
    } else {
        printf("最短路径长度为：%d\n", distance);
    }
    return 0;
}

以上代码中，我们使用了一个队列来存储待访问的坐标，使用二维数组 `visited` 记录已经访问过的坐标，使用二维数组 `distance` 记录起点到每个坐标的距离。在广度优先搜索算法中，我们每次取出队首元素，枚举其四个方向，对于每个方向，如果下一个坐标越界、是墙或已经访问过，则继续枚举下一个方向；否则，将下一个坐标入队，标记下一个坐标已经访问过，更新下一个坐标的距离。当取出的元素到达出口时，算法结束，返回最短路径长度。如果队列为空仍然没有找到出口，则说明迷宫没有出口。