題目描述
學(xué)霸搶走了大家的作業(yè)，班長為了幫同學(xué)們找回作業(yè)，決定去找學(xué)霸決斗。但學(xué)霸為了不要?jiǎng)e人打擾，住在一個(gè)城堡里，城堡外面是一個(gè)二維的格子迷宮，要進(jìn)城堡必須得先通過迷宮。因?yàn)榘嚅L還有妹子要陪，磨刀不誤砍柴功，他為了節(jié)約時(shí)間，從線人那里搞到了迷宮的地圖，準(zhǔn)備提前計(jì)算最短的路線。可是他現(xiàn)在正向妹子解釋這件事情，于是就委托你幫他找一條最短的路線。
輸入
第一行兩個(gè)整數(shù)n， m，為迷宮的長寬。
接下來n行，每行m個(gè)數(shù)，數(shù)之間沒有間隔，為0或1中的一個(gè)。0表示這個(gè)格子可以通過，1表示不可以。假設(shè)你現(xiàn)在已經(jīng)在迷宮坐標(biāo)(1,1)的地方，即左上角，迷宮的出口在(n,m)。每次移動(dòng)時(shí)只能向上下左右4個(gè)方向移動(dòng)到另外一個(gè)可以通過的格子里，每次移動(dòng)算一步。數(shù)據(jù)保證(1,1)，(n,m)可以通過。
輸出
第一行一個(gè)數(shù)為需要的最少步數(shù)K。
第二行K個(gè)字符，每個(gè)字符∈{U,D,L,R},分別表示上下左右。如果有多條長度相同的最短路徑，選擇在此表示方法下字典序最小的一個(gè)。
樣例輸入
3 3
001
100
110
樣例輸出
4
RDRD
提示
有20%的數(shù)據(jù)滿足：1<=n,m<=10

有50%的數(shù)據(jù)滿足：1<=n,m<=50

有100%的數(shù)據(jù)滿足：1<=n,m<=500
思路：其實(shí)單純的bfs就可以了，這個(gè)題目跟19年省賽填空壓軸題一樣。當(dāng)時(shí)一哥們說，怕用bfs會(huì)內(nèi)存超限。因此我試了試dfs。bfs找出最短路徑之后，記錄下來路徑。然后dfs再回去找路徑。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=5e2+10; struct node{int x,y;node(int a,int b){x=a,y=b;} }; int d[][2]={{1,0},{0,-1},{0,1},{-1,0}}; char rr[]={'D','L','R','U'}; char b[maxx][maxx]; int pre[maxx][maxx]; int vis[maxx][maxx]; int n,m;inline void bfs(int x,int y) {queue<node> q;q.push(node(x,y));vis[x][y]=1;while(q.size()){node a=q.front();q.pop();if(a.x==n&&a.y==m) break;for(int i=0;i<4;i++){int tx=a.x+d[i][0];int ty=a.y+d[i][1];if(tx<1||tx>n||ty<1||ty>m||b[tx][ty]=='1'||vis[tx][ty]) continue;vis[tx][ty]=1;pre[tx][ty]=i;q.push(node(tx,ty));}} } inline void dfs(int x,int y,string &s) {if(x==1&&y==1) return ;s=rr[pre[x][y]]+s;int tx=x-d[pre[x][y]][0];int ty=y-d[pre[x][y]][1];dfs(tx,ty,s); } int main() {scanf("%d%d",&n,&m);getchar();for(int i=1;i<=n;i++){for(int j=1;j<=m;j++) scanf("%c",&b[i][j]);getchar();}bfs(1,1);string s="";dfs(n,m,s);cout<<s.length()<<endl<<s<<endl;return 0; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的[蓝桥杯][算法提高VIP]学霸的迷宫（bfs+dfs）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。