迷宫问题是一种基础的算法问题,需要通过编程实现在一个迷宫中找到从起点到终点的路线。通常使用深度优先搜索或广度优先搜索算法来解决这个问题(主要是使用递归回溯和栈)
具体步骤如下:
1.定义一个二维数组表示迷宫,其中 0 表示可以通过的路,1 表示障碍物。
2.定义起点和终点坐标。
3.使用深度优先搜索或广度优先搜索算法在迷宫中搜索路径,记录经过的路径。
4.如果搜索到终点,则返回路径,否则返回无解。
代码及注释如下
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> //迷宫问题 //用结构体存迷宫的坐标 typedef struct Maze { int row; int col; }PT; //由于C语言没有栈的库,所以用‘-’分隔一下栈相关的代码 //------------------------------------------------------------------- typedef PT Type;//Tpye表示的是PT结构体类型 typedef struct Stack { Type* a; int top;//栈顶 int capacity;//容积 }ST; void StackInit(ST* ps); void StackDestory(ST* ps); //栈顶插入删除数据 //入栈 void StackPush(ST* ps, Type x); //出栈 void StackPop(ST* ps); Type StackTop(ST* ps); int StackSize(ST* ps); bool StackEmpty(ST* ps); //初始化 void StackInit(ST* ps) { assert(ps); ps->a = (Type*)malloc(sizeof(Type) * 4); if (ps->a == NULL) { printf("扩容失败\n"); exit(-1); } ps->capacity = 4; ps->top = 0; } //销毁 void StackDestory(ST* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; } //栈顶插入删除数据 //入栈(插入) void StackPush(ST* ps, Type x) { assert(ps); //满了就增容 if (ps->top == ps->capacity) { Type* tmp = realloc(ps->a, ps->capacity * 2 * sizeof(Type)); if (tmp == NULL) { printf("扩容失败\n"); exit(-1); } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; } //出栈(删除) void StackPop(ST* ps) { assert(ps); //栈空了,直接终止 assert(ps->top > 0); ps->top--; } // Type StackTop(ST* ps) { assert(ps); assert(ps->top > 0); return ps->a[ps->top - 1]; } //求数据个数 int StackSize(ST* ps) { assert(ps); return ps->top; } // bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } ST path;//定义一个全局的栈,用来存放迷宫路径位置的坐标 //---------------------------------------------------------------------------- //输出坐标 //(由于我们把坐标存入栈时的顺序和题目要求的顺序一样,就会导致出栈时坐标是反着出的 //,因此就需要倒置栈中的元素)【具体操作就看下面的PrintPath函数】 void PrintPath()//由于path是全局变量,就不需要再传参了 { //将栈里元素入到另外一个栈里面 //再输出另外一个栈的元素,就实现了倒置 ST rpath;//用这个栈来输出 StackInit(&rpath);//初始化栈 while (!StackEmpty(&path))//把path中的元素入到rpath中来 { StackPush(&rpath, StackTop(&path)); StackPop(&path); } while (!StackEmpty(&rpath))//再输出rpath中的元素,就就实现了倒置 { PT top = StackTop(&rpath); printf("(%d,%d)\n", top.row, top.col); StackPop(&rpath); } StackDestory(&rpath); } //测试迷宫图是否正确(不写这个函数也行) void PrintMaze(int** maze, int n, int m) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { printf("%d ", maze[i][j]); } printf("\n"); } } //判断该位置是否能走 int IsPass(int** maze, int n, int m, PT cur) { //坐标不能越界且该位置值为0 if (cur.col >= 0 && cur.row >= 0 && cur.col < m && cur.row < n && maze[cur.row][cur.col] == 0) { return 1; } else { return 0; } } //判断迷宫是否能走到出口(递归回溯) //(如果该位置能走通,就入栈,走不通(死路),就把该位置坐标弹出栈) int MazePath(int** maze, int n, int m, PT cur)//cur表示从迷宫走的起始位置坐标 { StackPush(&path, cur);//入栈 //如果走到出口 if (cur.row == n - 1 && cur.col == m - 1) { return 1; } //探测上下左右四个方向 PT next;//定义一个存放下一个位置坐标的结构变量 maze[cur.row][cur.col] = 2;//把走过的位置设为2,以防死递归 //上 next = cur; next.row -= 1; //如果下一个位置能走,就递归【上下左右同理】 if (IsPass(maze, n, m, next)) { if (MazePath(maze, n, m, next)) return 1; } //下 next = cur; next.row += 1; if (IsPass(maze, n, m, next)) { if (MazePath(maze, n, m, next)) return 1; } //左 next = cur; next.col -= 1; if (IsPass(maze, n, m, next)) { if (MazePath(maze, n, m, next)) return 1; } //右 next = cur; next.col += 1; if (IsPass(maze, n, m, next)) { if (MazePath(maze, n, m, next)) return 1; } //如果上下左右都不通,就把该位置坐标弹出栈 StackPop(&path);//出栈 return 0; } int main() { int N = 0; int M = 0; while (scanf("%d %d", &N, &M) != EOF) { //动态开辟二维数组 int** maze = (int**)malloc(sizeof(int*) * N); for (int i = 0; i < N; i++) { maze[i] = (int*)malloc(sizeof(int) * M); } //输入 for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { scanf("%d", &maze[i][j]); } } StackInit(&path); PT str = { 0,0 }; if (MazePath(maze, N, M, str)) { //找到了 PrintPath(); } else { printf("未找到"); } StackDestory(&path); for (int i = 0; i < N; i++) { free(maze[i]); } free(maze); maze = NULL; } return 0; }
运行结果:
迷宫问题的意义
迷宫问题是一类经典的寻路问题,通常被用来测试和研究搜索算法、路径规划算法和人工智能等方面的技术。在现实生活中,迷宫问题的应用场景非常广泛,例如在物流配送中的路径规划、机器人导航、游戏设计和智力竞赛等方面都有应用。此外,解决迷宫问题可以锻炼人的逻辑思维、学习算法的实现和优化、提高计算机编程能力等。