使用C语言队列编写一个迷宫问题要求迷宫可随机产生
时间: 2024-03-05 21:54:49 浏览: 20
好的,下面是一个使用 C 语言队列实现的迷宫问题解决代码,其中迷宫可以随机生成:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#define ROW 10
#define COL 10
typedef struct {
int x;
int y;
} Point;
typedef struct {
Point data[ROW * COL];
int front;
int rear;
} Queue;
void initQueue(Queue *q) {
q->front = q->rear = 0;
}
bool isQueueEmpty(Queue *q) {
return q->front == q->rear;
}
void enqueue(Queue *q, Point p) {
q->data[q->rear++] = p;
}
Point dequeue(Queue *q) {
return q->data[q->front++];
}
bool isVisited[ROW][COL] = { false };
int maze[ROW][COL] = { 0 };
void generateMaze() {
srand((unsigned int)time(NULL));
for (int i = 1; i < ROW - 1; i++) {
for (int j = 1; j < COL - 1; j++) {
maze[i][j] = rand() % 2;
}
}
}
void printMaze() {
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; j++) {
printf("%d ", maze[i][j]);
}
printf("\n");
}
}
bool isWall(int x, int y) {
return maze[x][y] == 1;
}
bool isExit(int x, int y) {
return x == ROW - 1 && y == COL - 1;
}
bool isValid(int x, int y) {
return x >= 0 && x < ROW && y >= 0 && y < COL && !isVisited[x][y] && !isWall(x, y);
}
void findPath() {
Queue q;
Point start = { 0, 0 };
Point end = { ROW - 1, COL - 1 };
initQueue(&q);
enqueue(&q, start);
isVisited[start.x][start.y] = true;
while (!isQueueEmpty(&q)) {
Point p = dequeue(&q);
int x = p.x, y = p.y;
if (isExit(x, y)) {
printf("Found the path!\n");
return;
}
if (isValid(x + 1, y)) {
Point next = { x + 1, y };
isVisited[x + 1][y] = true;
enqueue(&q, next);
}
if (isValid(x, y + 1)) {
Point next = { x, y + 1 };
isVisited[x][y + 1] = true;
enqueue(&q, next);
}
if (isValid(x - 1, y)) {
Point next = { x - 1, y };
isVisited[x - 1][y] = true;
enqueue(&q, next);
}
if (isValid(x, y - 1)) {
Point next = { x, y - 1 };
isVisited[x][y - 1] = true;
enqueue(&q, next);
}
}
printf("Cannot find the path!\n");
}
int main() {
generateMaze();
printMaze();
findPath();
return 0;
}
```
这个代码会随机生成一个迷宫,然后使用队列来解决从起点到终点的路径问题。其中,`initQueue` 函数用于初始化队列,`isQueueEmpty` 函数用于判断队列是否为空,`enqueue` 函数用于将元素入队,`dequeue` 函数用于将队头元素出队。`isVisited` 数组用于记录每个点是否已经访问过,`maze` 数组用于存储迷宫的地图,0 表示路,1 表示墙。`generateMaze` 函数用于随机生成迷宫,`printMaze` 函数用于打印迷宫的地图。`isWall` 函数用于判断一个点是否是墙,`isExit` 函数用于判断一个点是否是出口。`isValid` 函数用于判断一个点是否是合法的访问点,即没有访问过且不是墙。`findPath` 函数使用 BFS 算法遍历迷宫,查找从起点到终点的路径。