资源描述：
《迷宫实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、实验内容3、迷宫问题。假设迷宫由m行n列构成，有一个出口和一个入口，入口坐标为（1,1），出口坐标为（m,n），试设计并验证以下算法：找出一条从入口通往出口的路径，或报告一个“无法通过”的信息。（1）用C语言实现顺序存储队列上的基本操作，然后利用该队列的基本操作找出迷宫的一条最短路径。（2）设计一个二维数组MAZE[m+2][n+2]表示迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE[1][1]、MAZE[m][n]分别为迷宫的入口和出口。（3）输入迷宫的大小m行和n列，动态生成二维数组；由随机数产生0或1，建立迷宫，注意m*n的迷
2、宫需要进行扩展，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙。（4）要求输出模拟迷宫的二维数组；若存在最短路径，则有出口回溯到入口（出队列并利用栈实现），再打印从入口到出口的这条路径，例如（1,1），......，（i,j），......，（m,n）；若没有路径，则打印“Nopath”。（5）迷宫的任一位置（i,j）上均有八个可移动的方向，用二维数组Direction存放八个方向的位置偏移量。Direction[8][2]={{0,1}，{1,1}，{0，-1}，{-1，-1}，{1,-1}，{1,0}，{-1,0}，{-1,1}}；（6）为避免出现原地
3、踏步的情况需要标志已经通过的位置，采用一个标志数组MARK[m+2][n+2]，初值均为0，在寻找路径的过程中，若通过了位置（i，j），则将MARK[i][j]置为1。（7）为了记录查找过程中到达位置（i，j）及首次到达（i,j）的前一位置（i_pre,j_pre），需要记住前一位置（i_pre,j_pre）在队列中的序号pre，即队列中数据元素应该是一个三元组（i,j,pre）。（8）搜索过程简单下：将入口MAZE[1][1]作为第一个出发点，依次在八个方向上搜索可通行的位置，将可通行位置（i,j,pre）入队，形成第一层新的出发点，然后依次出队，即对第一层中各个位置
4、分别搜索它所在八个方向上的可通行位置，形成第二层新的出发点，...，如此进行下去，直至达到出口MAZE[m][n]或者迷宫所有位置都搜索完毕为止。二、实验过程及结果一、需求分析1、用栈的基本操作完成迷宫问题的求解，其中栈的基本操作作为一个独立的模块存在。2、以二维数组M[m+2][n+2]表示迷宫，M[i][j]表示迷宫中相应（i,j）位置的通行状态（0:表示可以通行，1：表示有墙，不可通行），完成迷宫的抽象数据类型，包括出口、入口位置等。3、用户从屏幕上输入迷宫，从键盘输入迷宫的大小，即迷宫的长和宽(由于控制台大小限制，输入的长宽需在50以下)，完成对应迷宫的初始化。
5、根据键盘输入的迷宫规格随机生成大小相同的迷宫，产生方块的地方为墙，无方块的地方可通过，如下例所示：如下所示：4、程序完成对迷宫路径的搜索，为了更好地显示出求解结果，如果存在路径，则以长方形形式将迷宫打印出来，而不是只按步输出坐标，也便于检查路径的正确性，用特定符号标出迷宫的物理状态，其中字符“#”表示出口和入口，“<”标记出可行的路径；如果程序完成搜索后没有找到通路，则提示用户“NoPath!”。如图所示：5、程序执行的命令：⑴创建初始化迷宫；⑵搜索迷宫；⑶输出搜索到的最短路径。一、概要设计（按照题目要求应该用队列实现路径的存储，但操作过程中遇到很多困难未能解决，故选择
6、栈的操作来实现路径的存储）1、迷宫的抽象数据类型定义：ADTMaze{数据对象：D：={aij,Start,end
7、-20<=aij<20,Start,end∈{(i,j)
8、0≤i≤m+2,0≤j≤n+2,m,n≥0}}数据关系：R={length，width}length={
9、ai-1,aij∈Di=1,…,m+2,j=1,…,n+2}width={
10、aijaij-1∈D}基本操作:SetMaze(&M)初始条件：M已经定义，M的下属单元二维数组M.Maze[row+2][d+2]已存在，M.start,M.end也已作为下
11、属存储单元存在操作结果：构成数据迷宫，用数值标识迷宫的物理状态，以0表示通路，以1表示障碍，由终端读取迷宫空间大小，各点处的具体物理状态及Start和End点位置，完成迷宫构建Pass(M,CurPos)初始条件：已知目前迷宫状态及当前位置操作结果：完成相应的搜索任务，如果可行，则返回1NextPos(CurPos,directionr)操作结果：返回CurPOS位置在方向direction上的下一位置SameSeat(Path,row,col)操作结果：若（row，col）位置是路径Path中的一个点，则返回TRUEPrintMaze(
