实验二 迷宫实验.doc

一、实验目的1、掌握栈的定义、操作及应用。2、掌握数组的定义、操作及应用。3、了解建立迷宫问题数学模型的方法。4、了解解决迷宫问题的算法。二、实验仪器和设备1、微机2、MICROSOFTVC++、实验原理及内容迷宫是一个矩形区域,只有两个门,一个叫做入口,另一个叫做出口。在出口处放上一块奶酪,将一只老鼠放在迷宫的入口处,随后官迷入口处。老鼠必须在规定的时间内找到出口,否则会在迷宫中饿死。在迷宫的内部包含不能穿越的墙或障碍。障碍物沿着行和列放置,它们与迷宫的矩形边界平行。如下图所示。图2-1迷宫示意图用一个取值为{0,1,-1}的二维数组MAZE[M][N]表示迷宫,如果用[I][J]来表示老鼠处在迷宫中的第I行,第J列的位置,该位置值为1表示有障碍,值为0表示有通路,值为-1表示老鼠已经路过该位置,不能再次回到该位置,如下图所示。111111111111111111010001100011111111000110111001111101100001111001111110111101101100111101001011111111100110111010010111110110011111111110011011011111011111000110110000011001111100011110110100111110111101111111**********图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,direction)。然后将三元组存放在栈中,从而构成一个从入口处到出口处的通路栈。在行进过程中,若取了一个错误的方向则返回,并继续试探下一个方向。如果八个方向都有障碍,则应回到上一个位置继续探试。由于边界上的位置没有八个方向,为了避免检验每个位置是否在边界上,给迷宫加一个值为1的外边。由于老鼠不可能处在边界上的位置,因此老鼠可能路过的任何位置都有八个移动方向。四、实验步骤1、析迷宫问题,建立数学模型,确定求解方法,画出流程图。2、写解决迷宫问题的程序。如下代码是使用栈解决迷宫问题的完整程序。#include<>#include<>#include<>#defineROW11//定义入口#defineCOLUMN15typedefstruct{/*栈中的数据元素的类型定义*/ introw;/*行下标*/ intcol;/*列下标*/ intdirection;/*下一步移动方向*/}DATA;typedefstructnode{/*栈类定义*/ DATAdata; structnode*next;}LinkStack;typedefstruct {/*移动方向的坐标