迷宮問題的最短路，加最小字典序

迷宮文件maze.txt傳送門
作者寫的2019年B組藍橋杯解集
.
.
.

DFS的版本

#include<iostream> #include<cstring> using namespace std; const int ax[4]={0,0,1,-1}; const int ay[4]={1,-1,0,0}; const char dir[5]={'R','L','D','U'}; int maze[60][60],mins[60][60]; char a[2000]; int best; string ans; bool judge(int x,int y) {//判斷這個點是否越界，是否走過。if(x>0&&x<=30&&y>0&&y<=50&&!maze[x][y])return true;return false; } void dfs(int x,int y,int pos) {if(pos>best)return ;if(x==30&&y==50) {string temp;for(int i=1;i<pos;i++)temp+=a[i];if(pos<best) {//是最短的路ans=temp;best=pos;}else if(pos==best&&temp<ans) ans=temp;//在實現路時最短的同時，保證字典序最小。return ;}for(int i=0;i<4;i++) {int tempx=x+ax[i];int tempy=y+ay[i];if(judge(tempx,tempy)&&pos+1<=mins[tempx][tempy]) {maze[tempx][tempy]=1;mins[tempx][tempy]=pos+1;a[pos]=dir[i];dfs(tempx,tempy,pos+1);maze[tempx][tempy]=0;//回溯找短的路，或者時字典序最小的。}} } int main() {freopen("D:\\MY\\ce.txt","r",stdin);memset(mins,1,sizeof(mins));best=1<<28;for(int i=1;i<=30;i++)for(int j=1;j<=50;j++) {char t;cin>>t;maze[i][j]=t-'0'; }maze[1][1]=1;dfs(1,1,1);cout<<ans<<endl;return 0; }

其中最重要的就是數組mins,這里記錄了從起始位置到這里的最短步數，
l
l當這個點在可以到達終點的路徑上時，也有可能有多種方式到這個點，所以一點更要保證時最小的步數到可以到達終點的路徑上的點。
.
.
.
BFS版本

#include<iostream> #include<cstring> #include<queue> const int ax[4]={1,0,0,-1}; const int ay[4]={0,-1,1,0}; const char dir[5]={'D','L','R','U'}; int maze[40][60]; using namespace std; struct point {int x,y;string ans;point(int a,int b,string c):x(a),y(b),ans(c){} }; bool judge(int x,int y) {if(x>0&&x<=30&&y>0&&y<=50&&!maze[x][y])return true;return false; } void bfs() {queue<point>ans;ans.push(point(1,1,""));maze[1][1]=1;while(!ans.empty()) {point temp=ans.front();ans.pop();if(temp.x==30&&temp.y==50) {cout<<temp.ans<<endl;return ;}for(int i=0;i<4;i++) {int tempx=temp.x+ax[i];int tempy=temp.y+ay[i];if(judge(tempx,tempy)) {maze[tempx][tempy]=1;ans.push(point(tempx,tempy,temp.ans+dir[i]));}}} } int main() {freopen("D:\\MY\\ce.txt","r",stdin);for(int i=1;i<=30;i++)for(int j=1;j<=50;j++) {char t;cin>>t;maze[i][j]=t-'0'; }bfs();return 0; }

這里就不用考慮回溯的問題，不用考慮是不是最短路的問題，但是可能有一個是不是字典序最小需要考慮，
.
于是我把這里的dir方向數組設置成了"D L R U"的順序，保證了在步數最小的前提下最小字典序一定會最早出現。

DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR
*
**
**
*

---

還有一點要注意的就是，我這里 用的是int數組存地圖，地圖之間沒有空格，一定要先用char讀取，或者直接用char數組表示地圖。
.
就因為這個，我抑郁了好久,一直不知道哪里錯了。

總結

以上是生活随笔為你收集整理的[蓝桥杯2019初赛]迷宫-DFS、BFS两种方法的全部內容，希望文章能夠幫你解決所遇到的問題。

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