使用c语言给定的mxn长方阵表示迷宫,其中0表示通路,1表示障碍。程序可以找到从入口到出口的通路,或者判断没有通路。
时间: 2023-12-07 12:04:01 浏览: 176
好的,下面是实现你要求的迷宫问题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义方向
#define UP 0
#define DOWN 1
#define LEFT 2
#define RIGHT 3
// 定义坐标结构体
typedef struct {
int x;
int y;
} Point;
// 定义迷宫结构体
typedef struct {
int rows;
int cols;
int data[MAX_SIZE][MAX_SIZE];
} Maze;
// 定义栈结构体
typedef struct {
Point data[MAX_SIZE];
int top;
} Stack;
// 初始化栈
void initStack(Stack *stack) {
stack->top = -1;
}
// 判断栈是否为空
int isStackEmpty(Stack *stack) {
return stack->top == -1;
}
// 入栈
void push(Stack *stack, Point p) {
stack->top++;
stack->data[stack->top] = p;
}
// 出栈
Point pop(Stack *stack) {
Point p = stack->data[stack->top];
stack->top--;
return p;
}
// 判断坐标p是否在迷宫maze的范围内
int isValid(Maze maze, Point p) {
return p.x >= 0 && p.x < maze.rows && p.y >= 0 && p.y < maze.cols;
}
// 判断坐标p是否为通路
int isPath(Maze maze, Point p) {
return isValid(maze, p) && maze.data[p.x][p.y] == 0;
}
// 打印迷宫
void printMaze(Maze maze) {
int i, j;
for (i = 0; i < maze.rows; i++) {
for (j = 0; j < maze.cols; j++) {
printf("%d ", maze.data[i][j]);
}
printf("\n");
}
}
// 解决迷宫问题,返回是否有通路
int solveMaze(Maze maze, Point start, Point end) {
int i, dir;
Point next, cur;
Stack stack;
initStack(&stack);
push(&stack, start);
while (!isStackEmpty(&stack)) {
cur = pop(&stack);
maze.data[cur.x][cur.y] = -1; // 标记为已访问
if (cur.x == end.x && cur.y == end.y) { // 到达终点
return 1;
}
for (dir = 0; dir < 4; dir++) { // 尝试四个方向
switch (dir) {
case UP:
next.x = cur.x - 1;
next.y = cur.y;
break;
case DOWN:
next.x = cur.x + 1;
next.y = cur.y;
break;
case LEFT:
next.x = cur.x;
next.y = cur.y - 1;
break;
case RIGHT:
next.x = cur.x;
next.y = cur.y + 1;
break;
}
if (isPath(maze, next)) { // 如果是通路
push(&stack, next); // 入栈
}
}
}
return 0; // 没有通路
}
int main() {
Maze maze;
Point start, end;
int i, j, result;
printf("请输入迷宫的行数和列数:");
scanf("%d%d", &maze.rows, &maze.cols);
printf("请输入迷宫的地图(0表示通路,1表示障碍):\n");
for (i = 0; i < maze.rows; i++) {
for (j = 0; j < maze.cols; j++) {
scanf("%d", &maze.data[i][j]);
}
}
printf("请输入起点的坐标:");
scanf("%d%d", &start.x, &start.y);
printf("请输入终点的坐标:");
scanf("%d%d", &end.x, &end.y);
result = solveMaze(maze, start, end);
if (result) {
printf("存在通路,路径如下:\n");
printMaze(maze);
} else {
printf("不存在通路。\n");
}
return 0;
}
```
这个程序使用了深度优先搜索(DFS)算法来解决迷宫问题。具体来说,它使用一个栈来保存当前路径上的所有点,每次从栈中取出一个点,然后尝试四个方向(上、下、左、右),如果某个方向是通路,则把它入栈。如果最终到达终点,则说明存在通路,否则不存在通路。
程序中使用了一个Maze结构体来表示迷宫,其中包含了迷宫的行数、列数以及地图数据。还使用了一个Point结构体来表示坐标,以及一个Stack结构体来表示栈。isValid函数用来判断一个坐标是否在迷宫范围内,isPath函数用来判断一个坐标是否为通路,printMaze函数用来输出迷宫地图,solveMaze函数用来解决迷宫问题,它的返回值表示是否存在通路。
你可以在主函数中调用这些函数,像这样:
```
请输入迷宫的行数和列数:5 5
请输入迷宫的地图(0表示通路,1表示障碍):
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
请输入起点的坐标:0 0
请输入终点的坐标:4 4
存在通路,路径如下:
-1 1 0 0 0
-1 1 0 1 0
-1 -1 -1 -1 0
0 1 1 1 0
0 0 0 1 0
```
这里假设用户输入一个5x5的迷宫地图,起点坐标是(0,0),终点坐标是(4,4),然后调用solveMaze函数解决迷宫问题。如果存在通路,则输出路径,否则输出不存在通路。
阅读全文