利用C语言建立队列，实现迷宫求解。

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

#define MAX_SIZE 100 // 最大迷宫大小

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

typedef struct {
Position data[MAX_SIZE];
int front, rear;
} Queue;

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

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

bool isFull(Queue *q) { // 判断队列是否已满
return (q->rear + 1) % MAX_SIZE == q->front;
}

void enQueue(Queue *q, Position p) { // 元素入队
if (isFull(q)) {
printf("Queue is full.\n");
return;
}
q->data[q->rear] = p;
q->rear = (q->rear + 1) % MAX_SIZE;
}

Position deQueue(Queue *q) { // 元素出队
if (isEmpty(q)) {
printf("Queue is empty.\n");
return (Position) {-1, -1};
}
Position p = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return p;
}

bool isLegal(int maze[][MAX_SIZE], int row, int col, int rows, int cols) { // 判断当前位置是否合法
return row >= 0 && row < rows && col >= 0 && col < cols && maze[row][col] == 0;
}

void printPath(int maze[][MAX_SIZE], int rows, int cols, Position prev[][MAX_SIZE], Position start, Position end) { // 输出求解结果
if (prev[end.row][end.col].row == -1) {
printf("No solution found.\n");
return;
}
Position path[MAX_SIZE];
int count = 0;
Position cur = end;
while (cur.row != start.row || cur.col != start.col) { // 从终点回溯到起点，得到路径
path[count++] = cur;
cur = prev[cur.row][cur.col];
}
path[count++] = start;
printf("Path: ");
while (count) {
Position p = path[--count];
printf("(%d, %d) ", p.row, p.col);
if (count) {
printf("-> ");
}
if (maze[p.row][p.col] == 0) {
maze[p.row][p.col] = -1; // 将路径上的位置标识为-1
}
}
printf("\n");
}

void mazeSolver(int maze[][MAX_SIZE], int rows, int cols, Position start, Position end) { // 迷宫求解
int directions[][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 上下左右四个方向
Queue q;
init(&q);
bool visited[MAX_SIZE][MAX_SIZE] = {{false}}; // 标记是否已访问
Position prev[MAX_SIZE][MAX_SIZE] = {{{-1, -1}}}; // 记录每个位置的前驱位置
enQueue(&q, start);
visited[start.row][start.col] = true;
while (!isEmpty(&q)) { // 广度优先搜索
Position cur = deQueue(&q);
if (cur.row == end.row && cur.col == end.col) { // 若到达终点，则输出路径
printPath(maze, rows, cols, prev, start, end);
return;
}
for (int i = 0; i < 4; i++) { // 遍历四个方向
Position next = {cur.row + directions[i][0], cur.col + directions[i][1]};
if (isLegal(maze, next.row, next.col, rows, cols) && !visited[next.row][next.col]) {
enQueue(&q, next);
visited[next.row][next.col] = true;
prev[next.row][next.col] = cur;
}
}
}
printf("No solution found.\n");
}

int main() {
int maze[MAX_SIZE][MAX_SIZE], rows, cols;
printf("Please input the number of rows and columns of the maze:\n");
scanf("%d %d", &rows, &cols);
printf("Please input the maze:\n");
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
scanf("%d", &maze[i][j]);
}
}
Position start, end;
printf("Please input the start position (row, column):\n");
scanf("%d %d", &start.row, &start.col);
printf("Please input the end position (row, column):\n");
scanf("%d %d", &end.row, &end.col);
mazeSolver(maze, rows, cols, start, end);
printf("The maze after solving:\n");
for (int i = 0; i < rows; i++) { // 输出求解后的迷宫
for (int j = 0; j < cols; j++) {
printf("%d ", maze[i][j]);
}
printf("\n");
}
return 0;
}