Exp02 迷宮的求解

Author: Maskros

實驗目的

輸入迷宮，得到從入口到出口的(最短)路徑

實驗內容與要求

迷宮只有兩個門，一個叫做入口，另一個叫做出口。把一只老鼠從一個無頂蓋的大盒子的入口處趕進迷宮。迷宮中設置很多隔壁，對前進方向形成了多處障礙，在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口。求解迷宮問題，即找出從入口到出口的路徑。

實驗內容和實驗步驟

分別通過深度優先搜索 (dfs) 和廣度優先搜索 (bfs) 兩種方法來實現實驗要求

• 大體思路：
  • dfs $O(m?n)$？：
    • 結構體point 存儲點的信息，maze[][]存圖，visit[][]判斷是否訪問過，dir[4][2]用于存儲四個方向，便于查找
    • stack<point> s 棧用于存儲最終路徑
    • void dfs(int x,int y) 函數對坐標進行深度優先搜索，采用遞歸的思路，順著一條路猛找，找不到返回上一級結點，直到找到為止。
    • void printpoint() 函數用于打印路徑
    • void printmaze() 函數用于打印地圖
  • bfs $O(m+n)$？：
    • 結構體node 存儲點的信息，其中int l 表示從開始到該結點的距離，node father[][]數組用于存儲當前節點的上一步是哪個結點，便于輸出路徑，其余變量同dfs
    • queue<node> q 用于讀入可走的路徑，在bfs中使用
    • bool check(int x,int y) 函數用于判斷當前結點是否可走
    • int bfs(node s) 函數，結束標志為隊空，從當前結點依次遍歷可走的方向，如果可以繼續走就將可走結點入隊，如果走到終點即返回最短路徑長度
    • string to_string(int s) 函數用于將int類型轉為string類型，便于輸出路徑
    • void print()函數根據father[][]從終點逆推打印路徑
• 輸入形式：首先輸出兩個正整數 $m$ , $n$ , 表示迷宮的有 $n$ 行 $m$ 列，接下來輸入迷宮序列, 1 表示可以通過, 0 表示不能通過。
• 輸出形式：以 bfs 實現的為例，首先輸出最短路長度 $l_{min}$ , 接下來以 $(x_i,x_i)$ -> $(x_j,y_j) $ … 表示這條路徑，最后輸出地圖，用* 表示走過的路使結果更加直觀；沒有路徑則輸出-1

dfs實現(求一條路徑)

//presented by Maskros - 2021/04/21 //dfs #include<bits/stdc++.h> using namespace std; int m,n; char maze[20][20]; //map int vis[20][20]={0}; //check if visited int dir[4][2]={ //four directrions{0,-1},{-1,0},{0,1},{1,0} }; char ans[20][20]; struct point{ int x,y; //coordinatechar d; //Record directionpoint(){};point(int a,int b,char c):x(a),y(b),d(c){} }pp; char check(int x,int xx,int y,int yy){ //Check the direction of the pathif(xx>x) return 'D';if(xx<x) return 'U';if(yy>y) return 'R';if(yy<y) return 'L';return '\0'; } bool ed=false; stack <point> s; void dfs(int x,int y){ //Depth first searchif(x>=m||x<0||y>=n||y<0) return ; //Can't reachif(x==m-1&&y==n-1) {ed=true; return ;} //reach destinationint nx,ny;for(int i=0;i<4;i++){nx=x+dir[i][0];ny=y+dir[i][1];if((nx<m&&nx>=0&&ny<n&&ny>=0) && vis[nx][ny]==0 && maze[nx][ny]=='1'){vis[nx][ny]=1;dfs(nx,ny);if(ed==true){ s.push(point(nx,ny,check(x,nx,y,ny))); return ; } //Recursive search the path}} } void printpoint(){ //Print pathputchar('\n');char dd;bool st=false;while(!s.empty()){pp=s.top();s.pop();if(st) {dd=pp.d; cout<<dd<<")"<<endl;}else st=true;ans[pp.x][pp.y]='*';if(pp.x==m-1 && pp.y==n-1) dd='E';cout<<"("<<pp.y+1<<","<<pp.x+1<<",";}cout<<dd<<")"<<endl;return ; } void printmaze(){ //Print mapcout<<endl;for(int i=0;i<m;i++){for(int j=0;j<n;j++){cout<<ans[i][j]<<" ";}cout<<endl;}return; } int main(){cin>>m>>n;for(int i=0;i<m;i++)for(int j=0;j<n;j++){cin>>maze[i][j];ans[i][j]=maze[i][j];}if(maze[0][0]=='0'||m==0||n==0||maze[m-1][n-1]=='0'){cout<<"no way";return 0;} else {ans[0][0]='*';vis[0][0]=1;} dfs(0,0);if(ed==false) {cout<<"no way"<<endl; return 0;}else s.push(point(0,0,'\0'));printpoint();printmaze();return 0; }

bfs實現(求最短路)

//presented by Maskros - 2021/04/21 //bfs #include<bits/stdc++.h> using namespace std; int m,n; char maze[20][20]; //map int vis[20][20]={0}; //check if visited struct node{int x,y; //coordinateint l; //Path lengthnode(){}node(int a, int b):x(a),y(b),l(0){}node(int a, int b, int ll):x(a),y(b),l(ll){} }; node father[20][20]; //The previous node of the current node in the path queue<node> q; int dir[4][2]={ //four directions{0,-1},{-1,0},{0,1},{1,0} }; bool check(int x,int y){ //Judge if can goif(x>=0 && x<m && y>=0 && y<n && vis[x][y]==0 && maze[x][y]=='1')return true;else return false; }int bfs(node s){ //Breadth first search, based on queueint nx,ny;q.push(s);vis[s.x][s.y]=1;node tmp,next;while(!q.empty()){tmp=q.front();q.pop();if(tmp.x==m-1&&tmp.y==n-1) return tmp.l; //reach destinationfor(int i=0;i<4;i++){ //Look in four directions in turnnx=tmp.x+dir[i][0];ny=tmp.y+dir[i][1];if(check(nx,ny)) {next=node(nx,ny,tmp.l+1);father[nx][ny]=node(tmp.x,tmp.y); //Record the previous nodeq.push(next);vis[nx][ny]=1;}}}return -1; } string to_string(int s){ //Convert int to string and save in the pathstring l;while(s){int tmp=s%10;l=char(tmp+'0')+l;s/=10;}return l; } void print(){ //Print path and mapstring s="("+to_string(m)+","+to_string(n)+")";node tt=father[m-1][n-1];maze[m-1][n-1]='*';while(1){s="("+to_string(tt.x+1)+","+to_string(tt.y+1)+") -> "+s;maze[tt.x][tt.y]='*';if(tt.x==0 && tt.y==0) break;tt=father[tt.x][tt.y];}cout<<s<<endl<<endl;for(int i=0;i<m;i++){for(int j=0;j<n;j++){cout<<maze[i][j]<<" ";}cout<<endl;}return ; } int main(){cin>>m>>n;for(int i=0;i<m;i++){for(int j=0;j<n;j++){cin>>maze[i][j];}}if(!check(0,0)){ cout<<-1; return 0;} //Special caseint lmin=bfs(node(0,0)); //Shortest path lengthif(lmin==-1) cout<<-1;else {cout<<endl;cout<<"The length of the way is: "<<lmin<<endl;print();}return 0; }

實驗用測試數據和相關結果分析

Test 1 5 5 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1Test 2 1 1 1Test 3 1 5 1 1 0 1 1Test 4 4 4 1 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1Test 5 9 7 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 0 1

---

• 結果分析：無論是起點終點重合，沒有通路，以及對最短路的尋找均有正確的輸出

實驗總結

• 分別溫習了棧和隊列的使用，基于棧通過dfs遞歸爆搜出一條通路，以及基于隊列通過bfs逐漸找到一條最短路徑
• 干，時間復雜度有點不會算
• dfs 和 bfs 典中典，stl yyds

總結

以上是生活随笔為你收集整理的数据结构实验二：迷宫的求解的全部內容，希望文章能夠幫你解決所遇到的問題。

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