《數(shù)據(jù)結構編程《迷宮問題》.ppt》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構編程《迷宮問題》.ppt（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、迷宮問題,迷宮問題,主要內容 1問題分析 2遞歸算法 3非遞歸算法,1問題分析,,,,,,,,,,,,,,,,,1問題分析,迷宮求解 這是一個找出口的問題。自相似性表現(xiàn)在什么地方？ 每走一步的探測方式。 由于計算機很傻，只能通過窮舉方式找出口，怎么找法？沿著一個方向走下去，如果走不通，則換個方向走；四個方向都走不通，則回到上一步的地方，換個方向走；依次走下去，直到走到出口。,1問題分析,描述迷宮： 1、設置迷宮為二維數(shù)組，數(shù)組的值是 -1：代表墻 0： 代表未走過的路徑 1：代表走不通的路徑 2：代表路徑,1問題分析,1問題分析,2、設置搜索方向順序是東、南、西、北,,
2、,(x,y),(x-1,y),(x,y-1),(x,y+1),(x+1,y),,,,,東,北,2遞歸算法,明確遞歸函數(shù)的意義 每一步的走法 int next(int arr10,Point cur, Point end)；,迷宮求解,每走一步： 1、如果當前位置=出口，結束 2、否則： 假設當前位置為路徑； 如果東面未走過：向東走一步 如果南面未走過：向南走一步 如果西面未走過：向西走一步 如果北面未走過：向北走一步 設置當前位置走不通，回溯,int next(int arr10,Point cur,Point end) if((cur.x==end.x) ,
3、3非遞歸算法,程序步驟： 1、當前位置入棧 2、判斷下一步是否可通，“可通”則返回步驟1; “不可通”，換方向繼續(xù)探索; 3、若四周“均無通路”，則當前位置出棧，從前一位置換方向搜索。,void MasePath(int arr10,Point start,Point end) Stack PointStack; Point P=start; arrP.xP.y = 2; do PointStack.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
4、(arrP.xP.y-1==0) arrP.x--P.y =2; else if (arrP.x-1P.y==0)arr--P.xP.y = 2; else P = PointStack.Pop(); arrP.xP.y = 1; P = PointStack.Pop(); while ((P.x!=end.x) || (P.y!=end.y)); ,輔助函數(shù),//打印迷宮 void PrintPath(int arr10) for (int i=0;i<10;i++) for (int j=0;j<10;j++) if (arrij==-1) cout<<; else if (arrij==2) cout<< *; else cout<<; cout<
數(shù)據(jù)結構編程《迷宮問題》.ppt
