第3章栈和队列第4讲-栈的应用-用栈求迷宫问题

1、2、用栈求解用栈求解迷宫问题迷宫问题 给定一个给定一个MN的的迷宫图迷宫图、入口与出口入口与出口、行走规则行走规则。求。求一条从指定入口到出口的路径。一条从指定入口到出口的路径。 所求路径必须是所求路径必须是简单简单路径路径，即，即路径不重复。路径不重复。1/20 行走规则行走规则：上、下、左、右相邻方块行走。其中：上、下、左、右相邻方块行走。其中（i，j）表示一个方块）表示一个方块方位方位0方位方位2方位方位1方位方位3i，ji-1，ji，j+1i，j-1i+1，j2/200 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9入入口口出出口口 例如，例如，M=8，N=8

2、，图，图中的中的每个每个方块，用方块，用空白空白表示表示通道，通道，用用阴影表示障碍物。为了阴影表示障碍物。为了算法算法方便，一般方便，一般在迷宫外围加上了在迷宫外围加上了一条围墙。一条围墙。一条迷宫路径一条迷宫路径3/20 设置一个迷宫设置一个迷宫数组数组mg，其中，其中每个元素表示一个方块每个元素表示一个方块的的状态，为状态，为0时表示对应方块时表示对应方块是是通道，为通道，为1时表示对应方块不时表示对应方块不可走。可走。4/20int mgM+2N+2= 1, 1,1,1,1,1,1,1,1, 1, 1, 0,0,1,0,0,0,1,0, 1, 1, 0,0,1,0,0,0,1,0, 1

3、, 1, 0,0,0,0,1,1,0,0, 1, 1, 0,1,1,1,0,0,0,0, 1, 1, 0,0,0,1,0,0,0,0, 1, 1, 0,1,0,0,0,1,0,0, 1, 1, 0,1,1,1,0,1,1,0, 1, 1, 1,0,0,0,0,0,0,0, 1, 1, 1,1,1,1,1,1,1,1, 1;0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9MN5/20在算法中用到的栈采用顺序栈在算法中用到的栈采用顺序栈存储存储结构，即将结构，即将栈定义为：栈定义为：typedef struct int i;/当前方块的行号当前方块的行号 int j;/

4、当前方块的列号当前方块的列号 int di;/di是下一可走相邻方位的方位号是下一可走相邻方位的方位号 Box;/定义方块类型定义方块类型typedef struct Box dataMaxSize; int top;/栈顶指针栈顶指针 StType;/定义顺序栈类型定义顺序栈类型i，jx，ydi6/20试探顺序：试探顺序：从方位从方位0开始，顺时针开始，顺时针方向方向方位方位0方位方位2方位方位1方位方位3i，ji- -1，ji，j+1i，j- -1i+1，j7/20i，jijdiij- -1栈栈将将（i，j，- -1）进栈）进栈初始初始时，入口时，入口（i，j）作为当前方块。）作为当前方块

5、。所有走过的方块都会进栈！所有走过的方块都会进栈！8/20 如果一个当前方块如果一个当前方块（i，j）找到一个相邻可走方块）找到一个相邻可走方块（x，y），），就就继续从继续从（x，y）走下去。）走下去。i，jx，y方位方位dijdiijd栈栈将将（x，y，- -1）进栈）进栈xy- -19/20 如果一个当前方块如果一个当前方块（i，j）没有找到任何相邻可）没有找到任何相邻可走走方块，表方块，表示示此时此时无路无路可可走走，将，将其退栈。其退栈。i，jijdiijd栈栈将将（i，j，d）退栈）退栈10/20求解迷宫路径的求解迷宫路径的过程：过程：前一方块前一方块当前方块当前方块回溯回溯找其他

6、可能的相邻方块找其他可能的相邻方块所有相邻方块都不能走所有相邻方块都不能走11/20bool mgpath(int xi,int yi,int xe,int ye)/求解路径为求解路径为:(xi,yi)-(xe,ye) Box pathMaxSize, e; int i,j,di,i1,j1,k; bool find; StType *st;/定义栈定义栈st InitStack(st);/初始化栈顶指针初始化栈顶指针 e.i=xi; e.j=yi; e.di=-1;/设置设置e为入口为入口 Push(st,e);/方块方块e进栈进栈 mgxiyi=-1;/入口的迷宫值置为入口的迷宫值置为-1

7、避免重复走到该方块避免重复走到该方块用栈求一条迷宫路径的用栈求一条迷宫路径的算法算法： （xi，yi） （xe，ye） 0 1 2 3 4 50 1 2 3 4 5i j di11- -1一个栈一个栈为了为了避免避免重复，当重复，当一个方块进一个方块进栈栈时，时，将将迷宫值改为迷宫值改为- -112/20while (!StackEmpty(st)/栈不空时循环栈不空时循环 GetTop(st,e);/取栈顶方块取栈顶方块e i=e.i; j=e.j; di=e.di; if (i=xe & j=ye)/找到了找到了出口出口,输出输出该路径该路径 printf(一条迷宫路径如下一条迷宫

8、路径如下:n); k=0;while (!StackEmpty(st) Pop(st,e);/出栈方块出栈方块e pathk+=e;/将将e添加到添加到path数组中数组中13/20 while (k=1) k-; printf(t(%d,%d),pathk.i,pathk.j); if (k+2)%5=0) /每输出每每输出每5个方块后换一行个方块后换一行 printf(n); printf(n); DestroyStack(st);/销毁栈销毁栈 return true;/输出一条迷宫路径后返回输出一条迷宫路径后返回true i j di11- -1 112- -113- -124- -1

9、23- -1121233- -1 143- -1 144- -1 14/20 find=false; while (didatast-top.di=di; /修改原栈顶元素的修改原栈顶元素的di值值 e.i=i1; e.j=j1; e.di=-1; Push(st,e); /相邻可走方块相邻可走方块e进栈进栈 mgi1j1=-1;/(i1,j1)迷宫值置为迷宫值置为-1避免重复走到该方块避免重复走到该方块 从入口从入口（1,1）出发找到一个可走方）出发找到一个可走方块块（1，2）:将将（1，2，-1）进栈）进栈i j di111一个栈一个栈12-116/20 else/没有路径可没有路径可走走,则则退栈退栈 Pop(st,e);/将栈顶方块退栈将栈顶方块退栈mge.ie.j=0; /让退栈方块的位置变为其他路径可走方块让退栈方块的位置变为其他路径可走方块 DestroyStack(st);/销毁栈销毁栈 return false;/表示没有可走路径表示没有可走路径（2,4）方块没有通路）方块没有通路i j di一个栈一个栈24-1 退退栈栈疑难解答：这里不将mg栈顶方块设置为0，