资源描述:
《实验二 迷宫实验》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
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