《数据结构编程《迷宫问题》.ppt》由会员分享，可在线阅读，更多相关《数据结构编程《迷宫问题》.ppt（13页珍藏版）》请在三一办公上搜索。
1、迷宫问题,迷宫问题,主要内容 1问题分析 2递归算法 3非递归算法,1问题分析,1问题分析,迷宫求解 这是一个找出口的问题。自相似性表现在什么地方？每走一步的探测方式。由于计算机很傻，只能通过穷举方式找出口，怎么找法？沿着一个方向走下去，如果走不通，则换个方向走；四个方向都走不通，则回到上一步的地方，换个方向走；依次走下去，直到走到出口。,1问题分析,描述迷宫：1、设置迷宫为二维数组，数组的值是-1：代表墙 0：代表未走过的路径 1：代表走不通的路径 2：代表路径,1问题分析,1问题分析,2、设置搜索方向顺序是东、南、西、北,(x,y),(x-1,y),(x,y-1),(x,y+1),(x+1
2、,y),东,北,2递归算法,明确递归函数的意义 每一步的走法 int next(int arr10,Point cur,Point end)；,迷宫求解,每走一步：1、如果当前位置=出口，结束 2、否则：假设当前位置为路径；如果东面未走过：向东走一步 如果南面未走过：向南走一步 如果西面未走过：向西走一步 如果北面未走过：向北走一步 设置当前位置走不通，回溯,int next(int arr10,Point cur,Point end)if(cur.x=end.x),3非递归算法,程序步骤：1、当前位置入栈 2、判断下一步是否可通，“可通”则返回步骤1;“不可通”，换方向继续探索;3、若四周“
3、均无通路”，则当前位置出栈，从前一位置换方向搜索。,void MasePath(int arr10,Point start,Point end)Stack PointStack;Point P=start;arrP.xP.y=2;doPointStack.Push(P);if(arrP.xP.y+1=0)arrP.x+P.y=2;else if(arrP.x+1P.y=0)arr+P.xP.y=2;else if(arrP.xP.y-1=0)arrP.x-P.y=2;else if(arrP.x-1P.y=0)arr-P.xP.y=2;elseP=PointStack.Pop();arrP.xP.y=1;P=PointStack.Pop();while(P.x!=end.x)|(P.y!=end.y);,辅助函数,/打印迷宫void PrintPath(int arr10)for(int i=0;i10;i+)for(int j=0;j10;j+)if(arrij=-1)cout;else if(arrij=2)cout*;else cout;coutendl;coutendl;,
