《数据结构编程《迷宫问题》.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)
2、,(x+1,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;,