资源描述：
《利用栈实现迷宫的求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、利用栈实现迷宫的求解一、要解决的问题：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。二：算法基本思想描述:用一个字符类型的二维数组表示迷宫，数组中每个元素取值“0”（表示通路）或“1”（表示墙壁）。二维数组的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宫的边界；第1行第1列元素和第m行第n列元素置成“0”，表示迷宫的入口和出口走迷宫的过程可以模拟为一个搜索的过程：每到一处，总让它按东、南、西、北4个方向顺序
2、试探下一个位置；用二维数组move记录4个方向上行下标增量和列下标增量，则沿第i个方向前进一步，可能到达的新位置坐标可利用move数组确定：Px=x+move[i][0]Py=y+move[i][1]如果某方向可以通过，并且不曾到达，则前进一步，在新位置上继续进行搜索；如果4个方向都走不通或曾经到达过，则退回一步，在原来的位置上继续试探下一位置。三：设计：1：数据结构的设计：（1）定义三元数组元素的结构typedefstructMazeDirect{intDx;//行标intDy;//列标intdirect;//走到下一个
3、坐标点的方向}MazeDirect;（2）定义链表节点的结构组成typedefstructLinkNode{elemtypedata;//数据域structLinkNode*next;//指针域}LinkNode;（3）定义链栈的头指针typedefstruct{LinkNode*top;//栈的头指针}LinkStack;（4）移动数组结构的定义typedefstruct{intx,y;//x为行标，y为列标}Direction_increm;2：算法的设计：【1】迷宫图的设计设迷宫为m行n列，利用maze[m][n]来
4、表示一个迷宫，maze[i][j]=0或1;其中：0表示通路，1表示不通，当从某点向下试探时，中间点有4个方向可以试探，（见图）而四个角点有2个方向，其它边缘点有3个方向，为使问题简单化我们用maze[m+2][n+2]来表示迷宫，而迷宫的四周的值全部为1。这样做使问题简单了，每个点的试探方向全部为4，不用再判断当前点的试探方向有几个，同时与迷宫周围是墙壁这一实际问题相一致。假设有6行8列的迷宫，如下图为maze[8][10]构造的迷宫11111111111011101111100101111110000000111001
5、101111110001000110110001011111111111【2】试探方向的设计：在上述表示迷宫的情况下，每个点有4个方向去试探，如当前点的坐标(x,y)，与其相邻的4个点的坐标都可根据与该点的相邻方位而得到，如图2所示。因为出口在（m，n），因此试探顺序规定为：从当前位置向前试探的方向为从正东沿顺时针方向进行。为了简化问题，方便的求出新点的坐标，将从正东开始沿顺时针进行的这4个方向（用0，1，2，3表示东、南、西、北）的坐标增量放在一个结构数组move[4]中，在move数组中，每个元素有两个域组成，x：横坐
6、标增量，y：纵坐标增量。Move数组如图3所示。move数组定义如下：typedefstruct{intx;//行inty;//列}item;itemmove[4];这样对move的设计会很方便地求出从某点(x，y)按某一方向v(0≤v≤3)到达的新点（i，j）的坐标：i=x+move[v].x，j=y+move[v].y。(x，y)图2与点(x，y)相邻的4个点及坐标(x，y+1)(x，y-1)(x+1，y)(x-1，y)xy00111020-13-10图3增量数组move【3】栈的设计：当到达了某点而无路可走时需返回前
7、一点，再从前一点开始向下一个方向继续试探。因此，压入栈中的不仅是顺序到达的各点的坐标，而且还要有从前一点到达本点的方向，即每走一步栈中记下的内容为(行，列，来的方向)。对于图1所示迷宫，依次入栈为：top—>3,4,03,3,03,2,12,2,02,1,11,1,0栈中每一组数据是所到达的每点的坐标及从该点沿哪个方向向下走的，对于图3迷宫，走的路线为：(1,1,0)à(2,1,1)à(2,2,0)à(3,2,1)à(3,3,0)à(3,4,0)（下脚标表示方向），当无路可走，则应回溯，对应的操作是出栈，沿下一个方向即方向
8、继续试探。栈中元素是一个由行、列、方向组成的三元组，栈元素的设计如下：typedefstruct{intx,y,d;/*横纵坐标及方向*/}datatype;栈的定义为：SeqStacks;【4】.如何防止重复到达某点，以避免发生死循环：一种方法是另外设置一个标志数组mark[m][n]，它的所有元素都
