下载文档原格式
数据结构课程设计迷宫问题求解正文：一、引言在数据结构课程设计中，迷宫问题求解是一个经典且常见的问题。
迷宫问题求解是指通过编程实现在迷宫中找到一条从起点到终点的路径。
本文将详细介绍如何用数据结构来解决迷宫问题。
二、问题分析1.迷宫定义：迷宫是由多个格子组成的矩形区域，其中包括起点和终点。
迷宫中的格子可以是墙壁（无法通过）或者通道（可以通过）。
2.求解目标：在给定的迷宫中，找到从起点到终点的一条路径。
3.输入：迷宫的大小、起点坐标、终点坐标以及墙壁的位置。
4.输出：从起点到终点的路径，或者提示无解。
三、算法设计1.基础概念a) 迷宫的表示：可以使用二维数组来表示迷宫，数组的元素可以是墙壁、通道或者路径上的点。
b) 坐标系统：可以使用(x, y)来表示迷宫中各个点的坐标。
c) 方向定义：可以用上、下、左、右等四个方向来表示移动的方向。
2.深度优先搜索算法（DFS）a) 算法思想：从起点开始，沿着一个方向一直走到无法继续为止，然后回退到上一个点，再选择其他方向继续探索。
b) 算法步骤：i) 标记当前点为已访问。
ii) 判断当前点是否为终点，如果是则返回路径；否则继续。
iii) 遍历四个方向：1.如果该方向的下一个点是通道且未访问，则继续向该方向前进。
2.如果该方向的下一个点是墙壁或已访问，则尝试下一个方向。
iv) 如果四个方向都无法前进，则回退到上一个点，继续向其他方向探索。
3.广度优先搜索算法（BFS）a) 算法思想：从起点开始，逐层向外探索，直到找到终点或者所有点都被访问。
b) 算法步骤：i) 标记起点为已访问，加入队列。
ii) 循环以下步骤直到队列为空：1.取出队首元素。
2.判断当前点是否为终点，如果是则返回路径；否则继续。
3.遍历四个方向：a.如果该方向的下一个点是通道且未访问，则标记为已访问，加入队列。
iii) 如果队列为空仍未找到终点，则提示无解。
四、算法实现1.选择合适的编程语言和开发环境。
迷宫问题算法一、引言迷宫问题是一个经典的算法问题，对于寻找路径的算法有着广泛的应用。
迷宫是一个由通路和墙壁组成的结构，从起点出发，要找到通往终点的路径。
迷宫问题算法主要解决的是如何找到一条从起点到终点的最短路径。
二、DFS（深度优先搜索）算法深度优先搜索算法是迷宫问题求解中最常用的算法之一。
其基本思想是从起点开始，沿着一个方向不断向前走，当走到无法继续前进的位置时，回退到上一个位置，选择另一个方向继续前进，直到找到终点或者无路可走为止。
1. 算法步骤1.初始化一个空栈，并将起点入栈。
2.当栈不为空时，取出栈顶元素作为当前位置。
3.如果当前位置是终点，则返回找到的路径。
4.如果当前位置是墙壁或者已经访问过的位置，则回退到上一个位置。
5.如果当前位置是通路且未访问过，则将其加入路径中，并将其邻居位置入栈。
6.重复步骤2-5，直到找到终点或者栈为空。
2. 算法实现伪代码以下为DFS算法的实现伪代码：procedure DFS(maze, start, end):stack := empty stackpath := empty listvisited := empty setstack.push(start)while stack is not empty docurrent := stack.pop()if current == end thenreturn pathif current is wall or visited.contains(current) thencontinuepath.append(current)visited.add(current)for each neighbor in getNeighbors(current) dostack.push(neighbor)return "No path found"三、BFS（广度优先搜索）算法广度优先搜索算法也是解决迷宫问题的常用算法之一。
迷宫问题求解算法设计实验报告一、引言迷宫问题一直是计算机科学中的一个经典问题，其解决方法也一直是研究者们探讨的重点之一。
本实验旨在通过设计不同的算法，对迷宫问题进行求解，并对比不同算法的效率和优缺点。
二、算法设计1. 暴力搜索算法暴力搜索算法是最简单直接的求解迷宫问题的方法。
其基本思路是从起点开始，按照某种规则依次尝试所有可能的路径，直到找到终点或所有路径都被尝试过为止。
2. 广度优先搜索算法广度优先搜索算法也称为BFS（Breadth First Search），其基本思路是从起点开始，按照层次依次遍历每个节点，并将其相邻节点加入队列中。
当找到终点时，即可得到最短路径。
3. 深度优先搜索算法深度优先搜索算法也称为DFS（Depth First Search），其基本思路是从起点开始，沿着某一个方向走到底，再回溯到上一个节点继续向其他方向探索。
当找到终点时，即可得到一条路径。
4. A* 算法A* 算法是一种启发式搜索算法，其基本思路是综合考虑节点到起点的距离和节点到终点的距离，选择最优的路径。
具体实现中，可以使用估价函数来计算每个节点到终点的距离，并将其加入优先队列中。
三、实验过程本实验使用 Python 语言编写程序，在不同算法下对迷宫问题进行求解。
1. 数据准备首先需要准备迷宫数据，可以手动输入或从文件中读取。
本实验使用二维数组表示迷宫，其中 0 表示墙壁，1 表示路径。
起点和终点分别用 S 和 E 表示。
2. 暴力搜索算法暴力搜索算法比较简单直接，只需要按照某种规则遍历所有可能的路径即可。
具体实现中，可以使用递归函数来实现深度遍历。
3. 广度优先搜索算法广度优先搜索算法需要使用队列来存储待遍历的节点。
具体实现中，每次从队列中取出一个节点，并将其相邻节点加入队列中。
4. 深度优先搜索算法深度优先搜索算法也需要使用递归函数来实现深度遍历。
具体实现中，在回溯时需要将已经访问过的节点标记为已访问，防止重复访问。
出”。
四、栈的应用举例任何一个表达式都是由操作数、运算符和界限符组成的。
后两项统称为算符，算符集合命名为OP。
引入问题：如何用堆栈实现表达式求值？表达式求值有三种形式。
中缀表示：<操作数><运算符><操作数>前缀表示：<运算符><操作数><操作数>后缀表示：<操作数><操作数><运算符>以中缀表达式为例，进行重点讲解。
例2、用栈求解表达式21+44-3*6的值。
# 21+44-3*6#实现方法：设置一个运算符栈和一个操作数栈。
算符间的优先关系求值规则：1）先乘除,后加减；2）先括号内,后括号外；3）同类运算,从左至右。
约定：q1---栈顶的运算符q2---当前的运算符当q1=#，为开始符当q2=#，为结束符根据上述优先关系表，可见21+44-3*6#中‘-’ <‘*’，‘*’ >‘#’。
2、算法基本思想1）首先置‘#’为运算符栈的栈底元素, 操作数栈为空栈；2) 依次读入表达式中各个字符，如果判断为操作数则OPND栈，如21，44，进操作数栈；若为运算符θ2，则和OPTR的栈顶元素θ1比较优先级，θ1和θ2进行比较。
当θ1 < θ2 ，θ2 进栈；表达式21+44-3*6的算法编程实现。
[动画演示]1.5分钟结合算法演示系统，讲解用栈求解表达式21+44-3*6的算法执行过程。
[小结]2分钟栈的定义，栈的“先进后出”的特性；栈的顺序存储的实现；栈的应用。
当θ1 = θ2 ，θ1 出栈；若θ1 > θ2 ，θ1 出栈，先进行操作数求值；然后运算结果再进栈。
3、算法编程实现OperandType EvaluateExpression ( ){ InitStack(OPTR);push(OPTR,`#`);InitStack(OPND);read(w);Whi le NOT ((w=’#’)AND (GetTop(OPTR)= `#`) )[IF w NOT IN op THEN[ push(OPND,w); read(w);ELSE CASEPrecede(GetTop(OPTR),w)OF`<`:[ push(OPTR,c); read(w);]`=`: [pop(OPTR,x);if x=FUNCTION thenPUSH(OPND,x(POP(OPNE)));read(w);]`>`: [b:= pop(OPND);a:= pop(OPND);theta:= pop(OPTR);push(OPND,Operate(a,theta,b));]ENDC; ]RETURN(POP(OPND))ENDF;4、算法执行过程# 21+44-3*6#1）“#”先压入到运算符栈，即push(OPTR,`#`);OPTR OPND2）push(OPND,`21`)2）‘#’ <‘+’，push(OPTR, `+` );3）push(OPND,`44`)。
基本算法-回溯法（迷宫问题）作者：翟天保Steven版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处前言本文介绍一种经典算法——回溯法，可作为迷宫问题的一种解法，以下是本篇文章正文内容，包括算法简介、算法应用（迷宫问题）、算法流程和C++代码实现。
一、回溯法简介回溯法（Backtracking）是枚举法的一种，可以找出所有或者一部分的一般性算法，且有效避免枚举不对的解。
当发现某个解的方向不准确时，就不再继续往下进行，而是回溯到上一层，减少算法运行时间，俗称“走不通就回头换路走”。
特点是在搜索过程中寻找问题的解，一旦发现不满足条件便回溯，继续搜索其他路径，提高效率。
二、算法应用（迷宫问题）1.问题描述迷宫问题是回溯法的一种应用。
迷宫问题的描述为：假设主体（人、动物或者飞行器）放在一个迷宫地图入口处，迷宫中有许多墙，使得大多数的路径都被挡住而无法行进。
主体可以通过遍历所有可能到出口的路径来到达出口。
当主体走错路时需要将走错的路径记录下来，避免下次走重复的路径，直到找到出口。
主体需遵从如下三个原则：1.一次步进只能走一格；2.遇到路径堵塞后，退后直到找到另一条路径可行；3.走过的路径记录下来，不会再走第二次。
2.解题思路首先创建一个迷宫图，比如用二维数组人为定义MAZE[row][col]，MAZE[i][j]=1时表示有墙无法通过，MAZE[i][j]=0时表示可行，假设MAZE[1][1]为入口，MAZE[8][10]为出口，创建如下初始迷宫图：图1 初始迷宫图当主体在迷宫中前行时，有东南西北（即右下左上）四个方向可以选择，如下图所示：图2 方向示意图视情况而定，并不是所有位置都可以上下左右前进，只能走MAZE[i][j]=0的地方。
通过链表来记录走过的位置，并将其标记为2，把这个位置的信息放入堆栈，再进行下个方向的选择。
若走到死胡同且未到达终点，则退回到上一个岔路口选择另一个方向继续走。
了解迷宫问题的基本原理和规则迷宫问题是一个经典的谜题，其目标是找到从迷宫的入口到达出口的路径。
为了解决迷宫问题，我们首先需要了解其基本原理和规则。
迷宫结构和元素迷宫由一系列的房间、墙壁和通道组成。
房间表示迷宫的每个位置，墙壁则是房间之间的障碍物，而通道则是可以穿过的路径。
迷宫通常是一个二维方格结构，但也可以是其他形式，如图形迷宫。
入口和出口迷宫通常有一个入口和一个出口。
入口是迷宫的起点，而出口则是我们要到达的目标。
通常，入口位于迷宫的边缘，而出口可以位于任何位置，包括边缘或迷宫内部。
迷宫规则在解决迷宫问题时，我们需要遵循一些基本规则：1.只能通过通道移动：我们只能沿着通道前进，不能穿过墙壁。
2.不能走回头路：一旦通过某个通道进入下一个房间，我们不能返回前一个房间，除非通过其他路径。
3.探索所有可能性：为了找到正确的路径，我们需要尝试不同的选择，探索迷宫中的所有可能性。
解决迷宫问题的思路解决迷宫问题的一般思路包括以下步骤：1.观察迷宫结构：仔细观察迷宫的布局和元素，了解入口、出口以及房间之间的连接关系。
2.制定计划：在开始寻找路径之前，制定一个计划或策略。
可以尝试使用图形、手绘或思维导图等方式来规划解题步骤。
3.深度优先搜索：一种常见的解决迷宫问题的方法是深度优先搜索（DFS）。
它从入口开始，沿着一条路径一直向前，直到无法继续前进，然后回溯到上一个房间，选择其他路径继续探索。
4.广度优先搜索：另一种常用的方法是广度优先搜索（BFS）。
它从入口开始，逐层地向外扩展，先探索距离入口最近的房间，然后逐渐扩大搜索范围，直到找到出口。
5.使用递归：迷宫问题可以通过递归的方式解决。
通过定义适当的递归函数，我们可以将问题分解为更小的子问题，然后逐步解决每个子问题，最终找到整个迷宫的解。
了解迷宫问题的基本原理和规则是解决迷宫谜题的第一步。
通过掌握迷宫的结构、入口、出口以及遵循迷宫规则，我们可以制定有效的解题策略并使用适当的算法来找到正确的路径。
1. 迷宫程序设计5.1 主要功能：分析图象处理得到迷宫的01矩阵，找到迷宫出口和入口，并找出迷宫的路径。
（路径为连接出口和入口的一条近似为道路中线的坐标点集合）5.2 设计原理：最简单的，道路宽度为一个数据的迷宫采用回溯算法。
在每个点P处最多有三个方向可以继续走（三个方向都走不通才回溯倒退），根据设定的优先级选定一方向（选定某方向后就将该方向设置标志，以免重复），如果该方向下一点Q为道路则将点P入堆栈，并把当前位置设置为Q（同时将该位置设置标志，防止优先倒退），否则选取余下方向中的一个检测能否走。
当三个方向都走不通时，出栈回溯，当前位置点变成P点的上一个坐标点O，然后对O的未被标志的方向进行探测。
以此不断探测最终找出正确的路径。
实际处理得到的迷宫01矩阵，路的宽度有几十个数据。
为了得到近似路中间的那条路径，对基本的回溯算法进行了很多改进。
首先根据入口位置探测得到一半路宽对应的数据数量width，选取下一步前进方向首先选取当前前进的方向，当该方向上道路数据宽度小于width（实际编程时数据会适当放大）时说明路不通，要选取其它方向，并且该方向上路的数据宽度要大于width，所有方向都走不通则回溯。
5.3 算法框架：5.3 注意问题：1）为了保证路径为路的中间，在回溯出栈时要遇到转弯角要反复出栈，出栈次数为半路宽的数据点数量，以此避免在路边就转弯了。
2）在实际运行中，01矩阵并不是理想的那样，而是存在燥点和一些缺口等。
所以首先对01矩阵进行去燥点（将每个点与相邻部分点求算术和，由和值大小来判定该点是0还是1），在比较路宽等参数设置上根据实际环境情况会适当进行调整以获得最佳效果。
（注：专业文档是经验性极强的领域，无法思考和涵盖全面，素材和资料部分来自网络，供参考。
可复制、编制，期待你的好评与关注）。
栈和队列的应⽤——迷宫问题（深度、⼴度优先搜索）⼀、迷宫问题 给⼀个⼆维列表，表⽰迷宫（0表⽰通道，1表⽰围墙）。
给出算法，求⼀条⾛出迷宫的路径。
maze = [[1,1,1,1,1,1,1,1,1,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,0,0,1,1,0,0,1],[1,0,1,1,1,0,0,0,0,1],[1,0,0,0,1,0,0,0,0,1],[1,0,1,0,0,0,1,0,0,1],[1,0,1,1,1,0,1,1,0,1],[1,1,0,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1]] 1代表墙，0代表路，图⽰如下：⼆、栈——深度优先搜索 应⽤栈解决迷宫问题，叫做深度优先搜索（⼀条路⾛到⿊），也叫做回溯法。
1、⽤栈解决的思路 思路：从上⼀个节点开始，任意找下⼀个能⾛的点，当找不到能⾛的点时，退回上⼀个点寻找是否有其他⽅向的点。
使⽤栈存储当前路径。
后进先出，⽅便回退到上⼀个点。
2、⽤栈代码实现maze = [[1,1,1,1,1,1,1,1,1,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,1,0,0,0,1,0,1],[1,0,0,0,0,1,1,0,0,1],[1,0,1,1,1,0,0,0,0,1],[1,0,0,0,1,0,0,0,0,1],[1,0,1,0,0,0,1,0,0,1],[1,0,1,1,1,0,1,1,0,1],[1,1,0,0,0,0,0,0,0,1],[1,1,1,1,1,1,1,1,1,1]]# 四个移动⽅向dirs = [lambda x,y: (x+1, y), # 下lambda x,y: (x-1, y), # 上lambda x,y: (x, y-1), # 左lambda x,y: (x, y+1) # 右]def maze_path(x1, y1, x2, y2): # (x1,y1)代表起点；(x2,y2)代表终点stack = []stack.append((x1, y1))while(len(stack)>0):curNode = stack[-1] # 当前的节点(栈顶)if curNode[0] ==x2 and curNode[1] == y2: # 判断是否⾛到终点# ⾛到终点，遍历栈输出路线for p in stack:print(p)return True"""搜索四个⽅向"""for dir in dirs:nextNode = dir(curNode[0], curNode[1])# 如果下⼀个阶段能⾛if maze[nextNode[0]][nextNode[1]] == 0:stack.append(nextNode) # 将节点加⼊栈maze[nextNode[0]][nextNode[1]] = 2 # 将⾛过的这个节点标记为2表⽰已经⾛过了break # 找到⼀个能⾛的点就不再遍历四个⽅向else:# ⼀个都找不到，将该位置标记并该回退maze[nextNode[0]][nextNode[1]] = 2stack.pop()else:print("没有路")return Falsemaze_path(1,1,8,8)"""(1, 1) (2, 1) (3, 1) (4, 1) (5, 1) (5, 2) (5, 3) (6, 3) (6, 4)(6, 5) (7, 5) (8, 5) (8, 6) (8, 7) (8, 8)""" 总结算法就是：创建⼀个空栈，⾸先将⼊⼝位置进栈。
探索数学迷宫学习解决迷宫问题数学迷宫是一种富有挑战性和趣味性的问题，通过解决迷宫问题，我们不仅可以锻炼思维能力，还能在数学推理方面得到很大的提高。
本文将探索数学迷宫学习解决迷宫问题的方法和技巧。
1. 迷宫问题的基本定义数学迷宫问题是指在一个由通道和墙壁组成的方格图中，找到从起点到终点的路径。
迷宫问题中，起点和终点是已知的，而我们的任务就是找到一条从起点到终点的有效路径。
有效路径要求在到达终点之前，不能回退，只能选择向前、向左、向右或向下移动。
2. 搜索算法解决迷宫问题最常用的方法之一是搜索算法。
搜索算法有很多种，如深度优先搜索（DFS）和广度优先搜索（BFS）。
深度优先搜索是一种通过不断地向前搜索直到无法继续，然后回退到前一步的算法。
广度优先搜索则是一种逐层扩展搜索的算法。
这些算法可以通过递归或使用栈或队列进行实现。
3. 最短路径问题在迷宫问题中，我们通常不仅仅关注是否能够找到一条路径，还关注如何找到最短路径。
最短路径是指从起点到终点的路径中，所需步数最少的路径。
解决最短路径问题的常用算法是Dijkstra算法和A*算法。
Dijkstra算法通过计算每个节点的最短路径实现，而A*算法则是一种基于启发式搜索的算法，通过估计每个节点到终点的距离来选择下一步的移动方向。
4. 数学模型迷宫问题也可以转化为数学模型，从而应用更多的数学理论和算法进行解决。
可以使用图论中的图模型来表示迷宫，将每个方格看作图中的节点，将相邻的方格之间的通道看作节点之间的边。
然后，可以使用图论中的最短路径算法来解决迷宫问题。
5. 相关应用迷宫问题在现实生活中有许多应用。
例如，迷宫问题可以用来解决寻路问题，如无人驾驶车辆的路径规划、机器人的导航等。
此外，迷宫问题还可以应用于游戏设计中，设计出各种不同难度的迷宫关卡，给玩家带来挑战和乐趣。
总之，通过探索数学迷宫学习解决迷宫问题，我们可以培养逻辑思维和数学推理能力。
通过应用搜索算法、最短路径算法和数学模型，我们能够有效解决迷宫问题，并将此应用于更广泛的领域中。
堆栈迷宫求解#include<iostream>#include<malloc.h>#include<cstdlib> //随机数srand头文件#include<time.h> //time头文件#define OK 1#define OVERFLOW 0#define TRUE 1#define FALSE 0#define STACK_INIT_SIZE 100 //存储空间初始分配量#define STACKINCREMENT 10 //存储空间分配增量#define N 5using namespace std;typedef struct{int x,y;}PosType;//定义通道块位置坐标typedef struct{int ord; //通道块在路径上的“序号”PosType seat; //通道块在迷宫中的坐标位置int di; //从此通道块走向下一通道块的方向}SElemType; //栈的元素类型定义typedef struct{SElemType *base;SElemType *top;int stacksize; //当前已分配的存储空间}SqStack;//栈定义int arry[N][N];int Random(){int i,j,k;srand(unsigned(time(0)));arry[1][0]=arry[N-2][N-1]=0; //将入口、出口设置为“0”即可通过for(j=0;j<N;j++)arry[0][j]=arry[N-1][j]=1; //设置迷宫外围“不可走”，保证只有一个出口和入口for(i=2;i<N-1;i++)arry[i][0]=arry[i-1][N-1]=1; //设置迷宫外围“不可走”，保证只有一个出口和入口for(i=1;i<N-1;i++)for(j=1;j<N-1;j++){k=rand()%3; //随机生成0、1、2三个数if(k)arry[i][j]=0;else{if((i==1&&j==1)||(i==N-2&&j==N-2)) //距入口或出口一步的路是必经之路，故设该通道块为“0”加大迷宫能通行的概率arry[i][j]=0;elsearry[i][j]=1;}}return OK;}int InitStack(SqStack &s){ //构造一个空栈Ss.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!s.base)exit(OVERFLOW);//存储分配失败s.top=s.base;s.stacksize=STACK_INIT_SIZE;return OK;}int Push(SqStack &s,SElemType &e){ //插入e为新的栈顶元素if(s.top-s.base>=STACK_INIT_SIZE){//栈满,追加存储空间s.base=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeo f(SElemType));if(!s.base)exit(OVERFLOW);//存储分配失败s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;return OK;}int Pop(SqStack &s,SElemType &e){//若栈不空，删除S的栈顶元素if(s.base==s.top)return FALSE;e=*--s.top;return OK;}PosType NextPos(PosType &e,int dir){ //探索下一步PosType E;switch(dir){case 1:E.x=e.x; //向下E.y=e.y+1;break;case 2:E.x=e.x+1; //向右E.y=e.y;break;case 3:E.x=e.x; //向上E.y=e.y-1;break;case 4:E.x=e.x-1; //向左E.y=e.y;break;}return E;}int StackEmpty(SqStack s){//判断栈是否为空if (s.top==s.base)return OK;return OVERFLOW;}int MarkPrint(PosType e){ //留下不能通过的足迹arry[e.x][e.y]=3;return OK;}int Pass(PosType e){//当前块可否通过if (arry[e.x][e.y]==0) //0时可以通过return OK; // 如果当前位置是可以通过，返回1 return OVERFLOW; // 其它情况返回0}int FootPrint(PosType e){//留下通过的足迹arry[e.x][e.y]=7;return OK;}//迷宫函数// 若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中（从栈底到栈顶），并返回TRUE；否则返回FALSEint MazePath(int arry,PosType start,PosType end,SqStack &s){ PosType curpos;InitStack(s);SElemType e;int curstep;curpos=start; // 设定"当前位置"为"入口位置"curstep=1; // 探索第一步do{if(Pass(curpos)){ // 当前位置可通过，即是未曾走到过的通道块FootPrint(curpos); // 留下足迹e.di =1;e.ord = curstep;e.seat= curpos;Push(s,e); // 加入路径if(curpos.x==end.x&&curpos.y==end.y){cout<<"Good job！能到达终点!"<<endl; return TRUE;}curpos=NextPos(curpos,1); // 下一位置是当前位置的东邻curstep++; // 探索下一步}else{ // 当前位置不能通过if(!StackEmpty(s)){Pop(s,e);while(e.di==4&&!StackEmpty(s)){MarkPrint(e.seat);Pop(s,e);}if(e.di<4){e.di++;Push(s,e); // 留下不能通过的标记，并退回一步curpos=NextPos(e.seat,e.di); //当前位置设为新方向的相邻块}}}}while(!StackEmpty(s));cout<<"Sorry! 不能到达终点!"<<endl;return FALSE;}void PrintMaze(){//打印迷宫int i,j;for(i=0;i<N;i++){for(j=0;j<N;j++){if(arry[i][j]==0)cout<<" ";else if(arry[i][j]==1) cout<<"■"; //迷宫的“墙”else if(arry[i][j]==3)cout<<"◇"; //不通的路else if(arry[i][j]==7)cout<<"○"; //通过的路径}cout<<endl;}}void main(){SqStack S;PosType start,end;start.x=1;start.y=0; //起点坐标end.x=N-2;end.y=N-1; //终点坐标cout<<"\n==================迷宫游戏==================";cout<<"\n说明:■不能走的区域\t◇走不通的区域"; cout<<"\n “空格”代表未到过的区域";cout<<"\n ○代表能通过的路径，指向终点"; cout<<"\n------------------命令菜单------------------";cout<<"\n1.系统随机生成一个迷宫";cout<<"\n2.输入一个迷宫";cout<<"\n3.打印走出迷宫的路径";cout<<"\n4.退出游戏";cout<<"\n========================================== ==";cout<<"\n请输入您想执行的操作命令："<<endl; int n;while(cin>>n&&n){if(n==1){cout<<"系统将默认生成一个大小为"<<N<<"x"<<N<<"的迷宫:"<<endl;Random();MazePath(arry[N][N],start,end,S);PrintMaze();system("pause");cout<<"请输入您接下来要执行的操作命令："<<endl;}else if(n==2){cout<<"提示：此迷宫的大小须为"<<N<<"x"<<N<<":"&l t;<endl;cout<<"请输入迷宫："<<endl;for(int i=0;i<N;i++)for(int j=0;j<N;j++)cin>>arry[i][j];PosType s1,e1;cout<<"请输入入口坐标："<<endl;cin>>s1.x>>s1.y;cout<<"请输入出口坐标："<<endl;cin>>e1.x>>e1.y;MazePath(arry[N][N],s1,e1,S);PrintMaze();system("pause");cout<<"请输入您接下来要执行的操作命令："<<endl;}else if(n==3){PrintMaze();system("pause");cout<<"请输入您接下来要执行的操作命令："<<endl;}else if(n==4)break;else if(n!=1||n!=2||n!=3||n!=4)cout<<"输入错误，请您重新输入:"<<endl;}}。
