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

《數(shù)據(jù)結(jié)構(gòu)編程《迷宮問題》.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)編程《迷宮問題》.ppt（13頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

迷宮問題 迷宮問題 主要內(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ù)的意義每一步的走法intnext intarr 10 Pointcur Pointend 迷宮求解 每走一步 1 如果當(dāng)前位置 出口 結(jié)束2 否則 假設(shè)當(dāng)前位置為路徑 如果東面未走過 向東走一步如果南面未走過 向南走一步如果西面未走過 向西走一步如果北面未走過 向北走一步設(shè)置當(dāng)前位置走不通 回溯 intnext intarr 10 Pointcur Pointend if cur x end x 3 非遞歸算法 程序步驟 1 當(dāng)前位置入棧2 判斷下一步是否可通 可通 則返回步驟1 不可通 換方向繼續(xù)探索 3 若四周 均無通路 則當(dāng)前位置出棧 從前一位置換方向搜索 voidMasePath intarr 10 Pointstart 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 else P PointStack Pop arr P x P y 1 P PointStack Pop while P x end x P y end y 輔助函數(shù) 打印迷宮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 endl cout endl