资源描述：
《实验二 迷宫实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验二迷宫实验一、实验目的1、掌握栈的定义、操作及应用。2、掌握数组的定义、操作及应用。3、了解建立迷宫问题数学模型的方法。4、了解解决迷宫问题的算法。二、实验仪器和设备1、微机2、MICROSOFTVC++6.0三、实验原理及内容迷宫是一个矩形区域，只有两个门，一个叫做入口，另一个叫做出口。在出口处放上一块奶酪，将一只老鼠放在迷宫的入口处，随后官迷入口处。老鼠必须在规定的时间内找到出口，否则会在迷宫中饿死。在迷宫的内部包含不能穿越的墙或障碍。障碍物沿着行和列放置，它们与迷宫的矩形边界平行。如下图所示。图2－1迷宫示意图用一个取值为{0，1，-1}的二维数组MAZE[M][N]表示迷宫，如果
2、用[I][J]来表示老鼠处在迷宫中的第I行，第J列的位置，该位置值为1表示有障碍，值为0表示有通路，值为-1表示老鼠已经路过该位置，不能再次回到该位置，如下图所示。1111111111111111110100011000111111110001101110011111011000011110011111101111011011001111010010111111111001101110100101111101100111111111100110110111110111110001101100000110011111000111101101001111101111011111111111111
3、1111图2-2迷宫数组MAZE老鼠在[I][J]上的可能移动方向有8个，分别表示N（北）、NE（东北）、E（东）、SE（东南）、S（南）、SW（西南）、W（西）和NW（东北），如图2－3所示。图4－3移动方向示意图图2-3老鼠没到一个位置，就从北方向开始，按顺时针方向向查找其余各个方向，以决定走某一个方向。如果某个方向上的相邻位置为0，老鼠就可以沿着这个方向走；如果某个方向上的相邻位置为1或-1，表示有障碍或已经路过，老鼠就不能沿着这个方向走。将老鼠从入口到出口所经过的各个位置[i][j]，以及从该位置出发能到达下一个位置的方向direction组合起来，构成一个三元组（i,j,direc
4、tion）。然后将三元组存放在栈中，从而构成一个从入口处到出口处的通路栈。在行进过程中，若取了一个错误的方向则返回，并继续试探下一个方向。如果八个方向都有障碍，则应回到上一个位置继续探试。由于边界上的位置没有八个方向，为了避免检验每个位置是否在边界上，给迷宫加一个值为1的外边。由于老鼠不可能处在边界上的位置，因此老鼠可能路过的任何位置都有八个移动方向。四、实验步骤1、析迷宫问题，建立数学模型，确定求解方法，画出流程图。2、写解决迷宫问题的程序。如下代码是使用栈解决迷宫问题的完整程序。#include#include#include#d
5、efineROW11//定义入口#defineCOLUMN15typedefstruct{/*栈中的数据元素的类型定义*/introw;/*行下标*/intcol;/*列下标*/intdirection;/*下一步移动方向*/}DATA;typedefstructnode{/*栈类定义*/DATAdata;structnode*next;}LinkStack;typedefstruct{/*移动方向的坐标偏移值*/intx_offset;intx_offset;inty_offset;}DIRECTIONS;DIRECTIONSdir[8]={{-1,0},{-1,1},{0,1},{1,1
6、},{1,0},{1,-1},{0,-1},{-1,-1}};intmaze[ROW+2][COLUMN+2]={{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},{1,0,1,0,0,0,1,1,0,0,0,1,1,1,1,1,1},{1,1,0,0,0,1,1,0,1,1,1,0,0,1,1,1,1},{1,0,1,1,0,0,0,0,1,1,1,1,0,0,1,1,1},{1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,0,1},{1,1,1,0,1,0,0,1,0,1,1,1,1,1,1,1,1},{1,0,0,1,1,0,1,1,1,0,1,0,0
7、,1,0,1,1},{1,1,1,0,1,1,0,0,1,1,1,1,1,1,1,1,1},{1,0,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1},{1,1,1,0,0,0,1,1,0,1,1,0,0,0,0,0,1},{1,0,0,1,1,1,1,1,0,0,0,1,1,1,1,0,1},{1,0,1,0,0,1,1,1,1,1,0,1,1,1,1,0,1},{1,1,1,1,1,1,1,1
