c语言给定一迷宫以及入口和出口的坐标，要求寻找从入口到出口的最短距离。要求用到队列以及广度搜索来求

Question

比如下图假如入中是（0,0），出口是（1,7）黄色代表墙，白色代表通路，则从入口到出口的最短需要走8步。

求解答

Answer 1

引用chatgpt内容作答：
以下是一个使用广度优先搜索（BFS）算法来解决迷宫问题的C语言代码示例：

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

#define MAX_SIZE 45

typedef struct {
    int row;
    int col;
} Coordinate;

typedef struct {
    Coordinate coordinates[MAX_SIZE * MAX_SIZE];
    int front;
    int rear;
} Queue;

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

// 判断队列是否为空
bool isQueueEmpty(Queue *queue) {
    return queue->front == -1;
}

// 入队
void enqueue(Queue *queue, Coordinate coord) {
    if (isQueueEmpty(queue))
        queue->front = 0;
    queue->rear++;
    queue->coordinates[queue->rear] = coord;
}

// 出队
Coordinate dequeue(Queue *queue) {
    Coordinate coord = queue->coordinates[queue->front];
    if (queue->front == queue->rear)
        initQueue(queue);
    else
        queue->front++;
    return coord;
}

// 判断坐标是否合法
bool isValidCoordinate(int row, int col, int m, int n) {
    return row >= 0 && row < m && col >= 0 && col < n;
}

// 判断坐标是否为终点
bool isDestination(Coordinate coord, Coordinate destination) {
    return coord.row == destination.row && coord.col == destination.col;
}

// 寻找最短路径长度
int findShortestPath(int maze[MAX_SIZE][MAX_SIZE], int m, int n, Coordinate start, Coordinate destination) {
    int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向的偏移量

    bool visited[MAX_SIZE][MAX_SIZE] = {{false}}; // 记录每个坐标是否已访问
    visited[start.row][start.col] = true;

    Queue queue;
    initQueue(&queue);
    enqueue(&queue, start);

    int steps = 0; // 起点到当前坐标的步数

    while (!isQueueEmpty(&queue)) {
        int numNodesInLevel = queue.rear - queue.front + 1;

        while (numNodesInLevel > 0) {
            Coordinate current = dequeue(&queue);

            if (isDestination(current, destination))
                return steps;

            for (int i = 0; i < 4; i++) {
                int newRow = current.row + directions[i][0];
                int newCol = current.col + directions[i][1];

                if (isValidCoordinate(newRow, newCol, m, n) && maze[newRow][newCol] == 0 && !visited[newRow][newCol]) {
                    visited[newRow][newCol] = true;
                    Coordinate newCoord = {newRow, newCol};
                    enqueue(&queue, newCoord);
                }
            }

            numNodesInLevel--;
        }

        steps++;
    }

    return -1; // 无法到达终点
}

int main() {
    int m, n;
    scanf("%d %d", &m, &n);

    int maze[MAX_SIZE][MAX_SIZE];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &maze[i][j]);
        }
    }

    Coordinate start, destination;
    scanf("%d %d %d %d", &start.row, &start.col, &destination.row, &destination.col);

    int shortestPathLength = findShortestPath(maze, m, n, start, destination);

    if (shortestPathLength == -1)
        printf("nopath!\n");
    else
        printf("%d\n", shortestPathLength);

    return 0;
}

这个代码示例读取迷宫的大小、迷宫的内容以及起点和终点的坐标。然后使用广度优先搜索算法找到从起点到终点的最短路径长度，并输出结果。如果无法到达终点，则输出"nopath!"。请注意，代码中使用了一个队列来辅助实现广度优先搜索。