一、問題概述

?????? 之前，我們了解了如何實現迷宮問題（對于迷宮只有一個出口可以通的情況），事實上我們的迷宮有多個出口，對于每條路徑來說，有長有短，所以在這里，我們討論一下迷宮的最短路徑，即迷宮路徑的最優解問題。

二、解決方案

?????? 對于這樣一個迷宮：

???

?? 注：數字為0的表示可以通過，數字為1的表示不可以通過。

?? 從入口坐標：（2，0）開始，可以到達出口位置的通路總共有三條。可想而知，肯定得把每一條路徑都得遍歷一遍，記錄每條路徑的長度。我們這里采用了遞歸的思想。

求解最短路徑的辦法：

（1）將入口點標記起來，給其賦值；

（2）每次訪問的下一個位置就是前一個位置的值+1，直至一條路徑成功通往出口；

（3）如果訪問下一條路徑的時候，遞歸會回退，在這里回退時它還會檢測是否有通路，（上上節講迷宮問題時有具體實現，可以去參照），這時由于我們賦的值已經改變了，所以此時判斷的條件為如果它的下一個位置的值+1>當前的位置的值，它就可以通過。

（4）當每條路徑走完后，會顯示最后出口的值，這樣就知道哪條路徑最短啦。

圖示如下：

??????????????????????????????????????????????

三、實現代碼

//Maze1.h

#include<iostream> using namespace std; #include<assert.h> #include<stack>struct Pos {int _row;int _col; };void GetMaze(int *Maze,size_t N) {FILE* fout = fopen("Maze1.txt","r");assert(fout);for(size_t i = 0; i < N; ++i){for(size_t j = 0; j < N; ){int value = fgetc(fout);if(value == '1' || value == '0'){Maze[i*N+j] = value - '0';++j;}else if(value == EOF){cout<<"Maze error!"<<endl;return;}}} }bool IsCheckPath(int *maze,size_t n,Pos cur,Pos next) {if((next._row < 0 || next._row >= 10) || (next._col < 0 || next._col >= 10)||(maze[next._row*n+next._col] == 1)){return false;}if(maze[next._row*n+next._col] == 0){return true;}return maze[next._row*n+next._col]+1 > maze[cur._row*n+cur._col]; }//遞歸 void GetMazePath(int *maze,size_t n,Pos entry,stack<Pos>& s,stack<Pos>& ss) {Pos cur;Pos next;s.push(entry);next = entry;if(entry._row == n-1){if(ss.empty() || s.size() < ss.size()){ss = s;}s.pop();return;}//探測上下左右//上next = entry;cur = next;next._row-=1;if(IsCheckPath(maze,n,cur,next)){maze[next._row*n+next._col] = maze[cur._row*n+cur._col]+1;GetMazePath(maze,n,next,s,ss);}//右next = entry;cur = next;next._col+=1;if(IsCheckPath(maze,n,cur,next)){maze[next._row*n+next._col] = maze[cur._row*n+cur._col]+1;GetMazePath(maze,n,next,s,ss);}//下next = entry;cur = next;next._row+=1;if(IsCheckPath(maze,n,cur,next)){maze[next._row*n+next._col] = maze[cur._row*n+cur._col]+1;GetMazePath(maze,n,next,s,ss);}//左next = entry;cur = next;next._col-=1;if(IsCheckPath(maze,n,cur,next)){maze[next._row*n+next._col] = maze[cur._row*n+cur._col]+1;GetMazePath(maze,n,next,s,ss);}//四方都不通s.pop(); }void PrintMaze(int *maze,size_t n) {cout<<"迷宮顯示:>"<<endl;for(size_t i = 0; i < n; ++i){for(size_t j = 0; j < n; ++j){cout<<maze[i*n+j]<<" ";}cout<<endl;} }
//Maze1.cpp

#include"Maze1.h"//用棧和遞歸實現迷宮問題 const size_t N = 10;void FunTest() {int Maze[N][N];Pos entry = {2,0};stack<Pos> ss;stack<Pos> ss1;GetMaze((int*)Maze,N);Maze[entry._row][entry._col] = 2;GetMazePath((int*)Maze,N,entry,ss,ss1);cout<<"迷宮是否有出口？"<<!ss.empty()<<endl;PrintMaze((int*)Maze,N); }int main() {FunTest();return 0; }
四、運行結果

總結

以上是生活随笔為你收集整理的[数据结构]求解迷宫最短路径问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。