數(shù)據(jù)結(jié)構(gòu)編程《迷宮問題》.ppt

迷宮問題,迷宮問題,主要內(nèi)容 1問題分析 2遞歸算法 3非遞歸算法,1問題分析,1問題分析,迷宮求解 這是一個(gè)找出口的問題。自相似性表現(xiàn)在什么地方？ 每走一步的探測方式。 由于計(jì)算機(jī)很傻，只能通過窮舉方式找出口，怎么找法？沿著一個(gè)方向走下去，如果走不通，則換個(gè)方向走；四個(gè)方向都走不通，則回到上一步的地方，換個(gè)方向走；依次走下去，直到走到出口。,1問題分析,描述迷宮： 1、設(shè)置迷宮為二維數(shù)組，數(shù)組的值是 -1：代表墻 0： 代表未走過的路徑 1：代表走不通的路徑 2：代表路徑,1問題分析,1問題分析,2、設(shè)置搜索方向順序是東、南、西、北,(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、如果當(dāng)前位置=出口，結(jié)束 2、否則： 假設(shè)當(dāng)前位置為路徑； 如果東面未走過：向東走一步 如果南面未走過：向南走一步 如果西面未走過：向西走一步 如果北面未走過：向北走一步 設(shè)置當(dāng)前位置走不通，回溯,int next(int arr10,Point cur,Point end) if(cur.x=end.x) ,3非遞歸算法,程序步驟： 1、當(dāng)前位置入棧 2、判斷下一步是否可通，“可通”則返回步驟1; “不可通”，換方向繼續(xù)探索; 3、若四周“均無通路”，則當(dāng)前位置出棧，從前一位置換方向搜索。,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 (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<<endl; cout<<endl; ,