題目：

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

解題思路：

這個題是典型的BFS路徑問題，通過BFS即可獲得最短路徑長度，再通過尋找父節點的方式，獲得路徑。

#include <stdio.h>struct node{int x;int y;int s;int d;int p; }; int main(){char map[501][501], path[2500] = "";//此處為了方便設定了一個固定值，如果想節約內存空間，可以動態增加 int book[501][501] = {0};int n, m, head = 1, tail = 1, flag = 0;struct node que[2501];int next[4][3] = {{-1, 0, 'U'},//上U {1, 0, 'D'},//下D{0, -1, 'L'},//左L{0, 1, 'R'}//右R};int i, j,tx, ty;scanf("%d %d", &n, &m);for(i = 0; i < n; i++){scanf("%s", map[i]);}que[tail].x = 1;que[tail].y = 1;que[tail].s = 0;que[tail].p = 0;tail++;book[1][1] = 1;while(head < tail){if(flag){break;}for(i = 0; i < 4; i++){tx = que[head].x + next[i][0];ty = que[head].y + next[i][1];if(tx < 1 || ty < 1 || tx > n || ty > m){continue;} if(book[tx][ty] == 0 && map[tx - 1][ty - 1] == '0'){book[tx][ty] = 1;que[tail].x = tx;que[tail].y = ty;que[tail].s = que[head].s + 1;que[tail].d = next[i][2];que[tail].p = head; tail++; }if(tx == n && ty == m){flag = 1;break;}}head++;}i = tail - 1;j = 0;while(que[i].p != 0){path[j++] = que[i].d;i = que[i].p;}//輸出結果 printf("%d\n", que[tail - 1].s);for(j--; j >= 0; j--){printf("%c", path[j]);}return 0; }
在此感謝“T.H”，提供的測試數據。

博客名稱：王樂平博客
博客地址：http://blog.lepingde.com
CSDN博客地址：http://blog.csdn.net/lecepin

總結

以上是生活随笔為你收集整理的试题集—— 算法提高 学霸的迷宫的全部內容，希望文章能夠幫你解決所遇到的問題。

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