数据结构实验3.3：求解迷宫路径问题

文章目录

一，问题描述
二，基本要求
三，算法分析
- （一）整体思路
- （二）详细步骤
- - 1. 输入迷宫大小并生成迷宫
  - 2. 定义走步规则
  - 3. 深度优先搜索（DFS）
  - 4. 输出结果
- （三）复杂度分析
四，示例代码
五，实验操作
六，运行效果

一，问题描述

从一个迷宫的入口到出口找出一条通路。用一个二维数组 MAZE(1:m，1:n) 模拟迷宫，数组元素为 0 表示该位置可以通过，数组元素为 1 表示该位置不可以通行。MAZE(1，1) 和 MAZE(m，n) 分别为迷宫的入口和出口。

二，基本要求

（1）输入数据
① 输入迷宫的大小 m 行和 n 列，两者为整数；
② 由随机数产生 0 或 1，建立迷宫。
（2）走步规则：首先从向下开始，按照逆时针方向分别向右、向上、向左搜索下一步可能前进的位置
（3）输出数据
首先输出模拟迷宫的二维数组，若存在路径，则由出口回溯到入口打印这一条路径，如下所示：

          (m，n)， ……， (i，j)， ……， (1，1)

如无通道，则打印：“无路径！”

三，算法分析

（一）整体思路

本问题可采用深度优先搜索（DFS）算法结合栈结构来实现从迷宫入口到出口路径的查找。深度优先搜索的核心思想是沿着一条路径尽可能深地探索，直到无法继续前进，然后回溯到上一个节点，尝试其他可能的路径。使用栈来记录走过的路径，方便回溯操作。

（二）详细步骤

1. 输入迷宫大小并生成迷宫

首先，程序需要从用户处获取迷宫的行数 m 和列数 n。可以使用标准输入流 std::cin 来实现这一功能。之后，利用随机数生成器（如 <random> 库）为迷宫的每个位置随机赋予 0 或 1，以此构建迷宫。同时，要确保入口 MAZE[0][0] 和出口 MAZE[m - 1][n - 1] 的值为 0，保证可以从入口进入并有可能到达出口。

2. 定义走步规则

根据要求，走步顺序为向下、向右、向上、向左。可以使用一个二维数组来表示这四个方向的偏移量，示例如下：

const int directions[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

其中，每个元素表示在 x 和 y 方向上的偏移量。

3. 深度优先搜索（DFS）

初始化：创建一个栈用于记录路径，将入口 (0, 0) 压入栈中，并标记该位置已访问。可以使用一个二维布尔数组 visited 来记录每个位置是否被访问过。
搜索过程：当栈不为空时，取出栈顶元素作为当前位置，按照走步规则依次尝试四个方向的下一个位置：
- 检查下一个位置是否在迷宫范围内，是否为 0（可通行），并且是否未被访问过。
- 如果满足条件，则将该位置压入栈中，并标记为已访问。
- 如果当前位置是出口 (m - 1, n - 1)，则表示找到了一条路径，搜索结束。
- 如果四个方向都无法前进，则将当前位置从栈中弹出，回溯到上一个位置继续探索。

4. 输出结果

首先，输出模拟迷宫的二维数组，方便用户直观了解迷宫布局。
若栈中存储了从入口到出口的路径，则从栈顶开始依次输出路径上的每个位置，即从出口回溯到入口。
若栈为空，说明没有找到通路，输出 “无路径！”。

（三）复杂度分析

时间复杂度：在最坏情况下，需要遍历迷宫中的每个位置，因此时间复杂度为 $O (m * n)$ ，其中 m 是迷宫的行数，n 是迷宫的列数。
空间复杂度：主要的空间开销在于栈和 visited 数组，因此空间复杂度也为 $O (m * n)$ 。

四，示例代码

#define M 8
#define N 10
#define MAXS 100					// 栈的最大容量
#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define OK 1
#define ERROR 0
typedef int Status;typedef  struct {					// 定义位置坐标int x, y;
} PosType;typedef char MazeType[M + 2][N + 2];  	// 定义迷宫数组typedef struct {int  i;						// 当前位置的行下标int  j;						// 当前位置的列下标int  di;						// 下一个探索方向
} SElemType;typedef  struct {SElemType  st[MAXS];int top;
} Stack;// 查找迷宫路径的函数
Status  MazePath(MazeType maze, Stack *S, PosType start, PosType end) {int i, j, di, ftag;S->top++;S->st[S->top].i = start.x;S->st[S->top].j = start.y;S->st[S->top].di = -1;   // 入口进栈maze[start.x][start.y] = -1;				// 路径上的迷宫元素值置-1while (S->top > -1) {						// 栈非空循环i = S->st[S->top].i;j = S->st[S->top].j;di = S->st[S->top].di;  // 读栈顶元素if (i == end.x && j == end.y) {			// 已到出口，存在路径return OK;}ftag = 0;while (di < 4 && ftag == 0) {				// 找下一个可前进位置坐标i,jdi++;switch (di) {case 0: 						// 向下i = S->st[S->top].i + 1;j = S->st[S->top].j;break;case 1:						// 向右i = S->st[S->top].i;j = S->st[S->top].j + 1;break;case 2:						// 向上i = S->st[S->top].i - 1;j = S->st[S->top].j;break;case 3:						// 向左i = S->st[S->top].i;j = S->st[S->top].j - 1;break;}if (maze[i][j] == 0) {ftag = 1;}}if (ftag == 1) {						// 可以通过S->st[S->top].di = di;				// 修改栈顶元素的前进方向S->top++;S->st[S->top].i = i;S->st[S->top].j = j;S->st[S->top].di = -1;  // 新位置进栈maze[i][j] = -1;					// 做标记} else {								// 不能通过maze[S->st[S->top].i][S->st[S->top].j] = 0;	// 置为其它路径可通过此位置S->top--;						// 退栈}}return ERROR;
}int main() {MazeType  maze;int  i, j;Stack  S;S.top = -1;							// 初始化栈PosType  start = {1, 1}, end = {M, N};	// 入口、出口srand((unsigned)time(NULL));		// 用随机数生成迷宫数组for (i = 1; i <= M; i++) {for (j = 1; j <= N; j++) {maze[i][j] = rand() % 2;}}// 修正迷宫四周边沿初始化for (i = 0; i <= M + 1; i++) {maze[i][0] = 1;maze[i][N + 1] = 1;}for (j = 0; j <= N + 1; j++) {maze[0][j] = 1;maze[M + 1][j] = 1;}maze[1][1] = maze[M][N] = 0;			// 确保入口、出口可通过printf("迷宫输出：\n");				// 输出迷宫for (i = 1; i <= M; i++) {for (j = 1; j <= N; j++) {printf("%3d", maze[i][j]);}printf("\n");}if (MazePath(maze, &S, start, end)) {		// 迷宫求解printf("迷宫路径如下：\n");for (i = 0; i <= S.top; i++) {printf("  (%d,%d)", S.st[i].i, S.st[i].j);if ((i + 1) % 6 == 0) {printf("\n");}}printf("\n");} else {printf("  无路径！\n");}return 0;
}