用C语言编写迷宫问题:输入一个n×n的迷宫,定义左上角为起点,右下角为终点,寻找一条从起点到终点的路径。
时间: 2024-05-01 10:20:32 浏览: 36
以下是用C语言实现迷宫问题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义迷宫结构体
typedef struct {
int x; // 行
int y; // 列
} Point;
// 定义堆栈结构体
typedef struct {
Point data[MAX_SIZE];
int top;
} Stack;
// 初始化堆栈
void initStack(Stack *s) {
s->top = -1;
}
// 判断堆栈是否为空
int isEmpty(Stack *s) {
return s->top == -1;
}
// 判断堆栈是否已满
int isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
// 入栈
void push(Stack *s, Point p) {
if (isFull(s)) {
printf("Stack is full.\n");
exit(1);
}
s->data[++s->top] = p;
}
// 出栈
Point pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
exit(1);
}
return s->data[s->top--];
}
// 读取地图
void readMaze(int maze[][MAX_SIZE], int n) {
printf("Please input the maze (0 for path, 1 for wall):\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &maze[i][j]);
}
}
}
// 打印地图
void printMaze(int maze[][MAX_SIZE], int n) {
printf("The maze is:\n");
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
printf("%d ", maze[i][j]);
}
printf("\n");
}
}
// 查找路径
void findPath(int maze[][MAX_SIZE], int n) {
Stack s;
Point p = {0, 0}; // 起点
Point q = {n - 1, n - 1}; // 终点
int dir[][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; // 四个方向
int visited[MAX_SIZE][MAX_SIZE] = {0}; // 标记是否访问过
int found = 0; // 是否找到路径
initStack(&s);
push(&s, p); // 起点入栈
visited[p.x][p.y] = 1; // 标记为已访问
while (!isEmpty(&s) && !found) {
p = pop(&s);
for (int i = 0; i < 4; i++) { // 四个方向搜索
int dx = p.x + dir[i][0];
int dy = p.y + dir[i][1];
if (dx >= 0 && dx < n && dy >= 0 && dy < n && !visited[dx][dy] && !maze[dx][dy]) {
Point np = {dx, dy};
push(&s, np);
visited[dx][dy] = 1;
if (dx == q.x && dy == q.y) { // 如果找到终点
found = 1;
push(&s, q); // 终点入栈
break;
}
}
}
}
if (found) { // 打印路径
printf("The path is:\n");
while (!isEmpty(&s)) {
p = pop(&s);
printf("(%d, %d) ", p.x, p.y);
}
printf("\n");
} else {
printf("No path found.\n");
}
}
int main() {
int n;
int maze[MAX_SIZE][MAX_SIZE];
printf("Please input the size of maze (up to %d):\n", MAX_SIZE);
scanf("%d", &n);
readMaze(maze, n);
printMaze(maze, n);
findPath(maze, n);
return 0;
}
```
在程序中,定义了一个堆栈结构体和一个迷宫结构体。使用堆栈来实现深度优先搜索,使用迷宫结构体来记录每个点的坐标。在查找路径时,先将起点入栈,然后不断取出栈顶元素,对其四个方向进行搜索,将未访问的点入栈,并标记为已访问。如果找到终点,则将终点入栈,然后打印出路径;否则,输出“无路径”。
相关推荐
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)