堆栈-迷宫问题.ppt

《堆栈-迷宫问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、迷宫问题迷宫问题主要内容1．问题分析2．递归算法3．非递归算法1．问题分析o1．问题分析迷宫求解这是一个找出口的问题。自相似性表现在什么地方？每走一步的探测方式。由于计算机很傻，只能通过穷举方式找出口，怎么找法？沿着一个方向走下去，如果走不通，则换个方向走；四个方向都走不通，则回到上一步的地方，换个方向走；依次走下去，直到走到出口。1．问题分析描述迷宫：1、设置迷宫为二维数组，数组的值是-1：代表墙0：代表未走过的路径1：代表走不通的路径2：代表路径1．问题分析-1-1-1-1-1-1-1-1-1-1-100-1000

2、-10-1-100-1000-10-1-10000-1-100-1-10-1-1-10000-1-1000-10000-1-10-1000-100-1-10-1-1-10-1-10-1-1-10000000-1-1-1-1-1-1-1-1-1-1-11．问题分析2、设置搜索方向顺序是东、南、西、北(x,y)(x-1,y)(x,y-1)(x,y+1)(x+1,y)东北2．递归算法明确递归函数的意义每一步的走法intnext(intarr[][10],Pointcur,Pointend)；迷宫求解每走一步：1、如果当前位置

3、=出口，结束2、否则：假设当前位置为路径；如果东面未走过：向东走一步如果南面未走过：向南走一步如果西面未走过：向西走一步如果北面未走过：向北走一步设置当前位置走不通，回溯intnext(intarr[][10],Pointcur,Pointend){if((cur.x==end.x)&&(cur.y==end.y))return1;else{arr[cur.x][cur.y]=2;if(arr[cur.x+1][cur.y]==0)//东{Pointt;t.x=cur.x+1;t.y=cur.y;if(next(arr

4、,t,end))return1;}if(arr[cur.x][cur.y+1]==0)//南{Pointt;t.x=cur.x;t.y=cur.y+1;if(next(arr,cur,end))return1;}…//西…//北arr[cur.x][cur.y]=1;return0;}3．非递归算法程序步骤：1、当前位置入栈2、判断下一步是否可通，“可通”则返回步骤1;“不可通”，换方向继续探索;3、若四周“均无通路”，则当前位置出栈，从前一位置换方向搜索。voidMasePath(intarr[][10],Point

5、start,Pointend){StackPointStack;PointP=start;arr[P.x][P.y]=2;do{PointStack.Push(P);if(arr[P.x][P.y+1]==0)arr[P.x][++P.y]=2;elseif(arr[P.x+1][P.y]==0)arr[++P.x][P.y]=2;elseif(arr[P.x][P.y-1]==0)arr[P.x][--P.y]=2;elseif(arr[P.x-1][P.y]==0)arr[--P.x][P.y]=2;

6、else{P=PointStack.Pop();arr[P.x][P.y]=1;P=PointStack.Pop();}}while((P.x!=end.x)

7、

8、(P.y!=end.y));}辅助函数//打印迷宫voidPrintPath(intarr[][10]){for(inti=0;i<10;i++){for(intj=0;j<10;j++){if(arr[i][j]==-1)cout<<"■";elseif(arr[i][j]==2)cout<<"*";elsecout<<"□";}cout<

9、ut<