实验二 迷宫实验.doc

实验目的1、掌握栈的定义、操作及应用。2、掌握数组的定义、操作及应用。3、了解建立迷宫问题数学模型的方法。4、了解解决迷宫问题的算法。实验原理编写程序,利用栈、数组解决迷宫问题。本实验综合了栈、数组及数学建模等知识点,考察了学生对栈、数组等数据结构的理解和应用,使学生了解数学建模的基本方法。迷宫是一个矩形区域,只有两个门,一个叫做入口,另一个叫做出口。在出口处放上一块奶酪,将一只老鼠放在迷宫的入口处,随后关闭迷宫入口处。老鼠必须在规定的时间内找到出口,否则会在迷宫中饿死。在迷宫的内部包含不能穿越的墙或障碍。障碍物沿着行和列放置,它们与迷宫的矩形边界平行。如图4-1所示。图4-1迷宫示意图用一个取值为{0,1,-1}的二维数组maze[m][n]表示迷宫,如果用[i][j]来表示老鼠处在迷宫中的第i行,第j列的位置,该位置值为1表示有障碍,值为0表示有通路,值为-1表示老鼠已经路过该位置,不能再次回到该位置,如图4-2所示。111111111111111111010001100011111111000110111001111101100001111001111110111101101100111101001011111111100110111010010111110110011111111110011011011111011111000110110000011001111100011110110100111110111101111111**********图2迷宫数组maze老鼠在[i][j]上的可能移动方向有8个,分别表示N(北)、NE(东北)、E(东)、SE(东南)、S(南)、SW(西南)、W(西)和NW(东北),如图4-3所示。W[i][j-1][i][j]E[i][j+1]NE[i-1][j+1]SE[i+1][j+1]S[i+1][j]SW[i+1][j-1]N[i-1][j]NW[i-1][j-1]图4-3移动方向示意图老鼠每到一个位置,就从北方向开始,按顺时针方向向查找其余各个方向,以决定走某一个方向。如果某个方向上的相邻位置为0,老鼠就可以沿着这个方向走;如果某个方向上的相邻位置为1或-1,表示有障碍或已经路过,老鼠就不能沿着这个方向走。将老鼠从入口到出口所经过的各个位置[i][j],以及从该位置出发能到达下一个位置的方向direction组合起来,构成一个三元组(i,j,direction)。然后将三元组存放在栈中,从而构成一个从入口处到出口处的通路栈。在行进过程中,若取了一个错误的方向则返回,并继续试探下一个方向。如果八个方向都有障碍,则应回到上一个位置继续探试。由于边界上的位置没有八个方向,为了避免检验每个位置是否在边界上,给迷宫加一个值为1的外边。由于老鼠不可能处在边界上的位置,因此老鼠可能路过的任何位置都有八个移动方向。实验仪器和设备1、微机2、MicrosoftVC++、二维数组的定义、基本操作和存储结构。掌握栈、二维数组的C语言的实现。理解解决迷宫问题的算法原理。了解建立迷宫问题数学模型的基本方法。实验内容及步骤析迷宫问题,建立数学模型,确定求解方法,画出流程图。写解决迷宫问题的程序。如下代码是使用栈解决迷宫问题的完整程序。#include<>#include<>#def