2021年寒假每日一題，2017~2019年的省賽真題，本文內容由倪文迪（華東理工大學計算機系軟體192班）和羅勇軍老師提供，每日一題，關注藍橋杯專欄: https://blog.csdn.net/weixin_43914593/category_10721247.html

提供C++、Java、Python三種語言的代碼，

2019省賽A組第4題“迷宮” ，題目鏈接：
http://oj.ecustacm.cn/problem.php?id=1455

這一題是初學者訓練的好題目，

1、題目描述

下圖給出了一個迷宮的平面圖，其中標記為1 的為障礙，標記為0 的為可以通行的地方，
010000
000100
001001
110000
迷宮的入口為左上角，出口為右下角，在迷宮中，只能從一個位置走到這個它的上、下、左、右四個方向之一，
對于上面的迷宮，從入口開始，可以按DRRURRDDDR 的順序通過迷宮，一共10 步，其中D、U、L、R 分別表示向下、向上、向左、向右走，
對于下面這個更復雜的迷宮（30 行50 列），請找出一種通過迷宮的方式，其使用的步數最少，在步數最少的前提下，請找出字典序最小的一個作為答案，
請注意在字典序中D<L<R<U，

2、題解

??這題用來練習搜索很好！還有路徑列印，也需要掌握！

??圖雖然不大，但直接用手畫、拿眼睛看是數不出來了，只能編碼，這就是出題人的意思吧，
??不不不，有人說手畫、眼睛數能得到答案：https://www.bbsmax.com/A/kmzLkg9XdG/
??出題人還是善良了，這個迷宮其實不復雜，真的能用手數出來，

??本題圖不大，那么就是鼓勵用簡單的暴力搜索了，別想太多，
??是BFS還是DFS？
??（1）要搜所有可能的路徑嗎？不管用BFS還是DFS，復雜度都是指數的，
??（2）題目只要求搜最短路徑，這就簡單多了，肯定用BFS，BFS也是求最短路徑的一種經典演算法，不過，它僅用于相鄰結點距離為1的情況，這就是本題的情況，
??BFS原理，參考這篇博文的“3 BFS的性質和代碼實作”：
https://blog.csdn.net/weixin_43914593/article/details/104608578
??（3）最短路徑可能不止一條，不過并不復雜，BFS的特點是：它是逐層擴散的（往BFS的佇列中加入鄰居結點時，是按距離起點遠近的順序加入的：先加入距離起點為1的鄰居結點，加完之后，再加入距離為2的鄰居結點，等等），搜完一層，才會繼續搜下一層，一條路徑是從起點開始，沿著每一層逐步往外走，每多一層，路徑長度就增加了1，那么，所有長度相同的最短路徑都是從相同的層次擴散出去的，當搜到第一個到達終點的最短路徑后，繼續搜索，會回傳其他可能不是最短的路徑，
??（4）題目要求回傳字典序最小的最短路徑，那么只要在每次擴散下一層（往BFS的佇列中加入下一層的結點）時，都按字典序“D<L<R<U”的順序來加下一層的結點，那么第一個搜到的最短路徑就是字典序最小的那個，
??所以本題就是一個基本的BFS搜索最短路，復雜度只有 O ( n ) O(n) O(n)， n n n是迷宮內結點的總數，本題有 30 × 50 = 1500 30\times 50=1500 30×50=1500個點，因為每個點只用搜一次，即進入佇列和出佇列一次，
??本題另一個有用的地方是路徑列印，下面給出兩種列印方法，

3、兩種路徑列印方法

?? 路徑如何列印？一個簡單的辦法是：每擴展到一個點 v v v，都在 v v v上存盤從起點 s s s到 v v v的完整路徑 p a t h path path，到達終點 t t t時，就得到了從起點 s s s到 t t t的完整路徑，這樣做的缺點是會占用大量空間，因為每個點上都存盤了完整的路徑，
?? 其實不用在結點上存盤完整路徑，而是在每個點上記錄它的前驅結點就夠了，這樣從終點能一步步回溯到起點，得到一條完整路徑（詳細解釋見《演算法競賽入門到進階》245頁“列印最短路徑”），稱這種路徑記錄方法為“標準方法”，
?? 下面用代碼分別演示這兩種路徑列印方法，

3.1 簡單方法

?? 確實非常簡單，到達終點后，用cout<<now.p<<endl;一句就列印出了完整路徑，
??（注意，下面2個代碼，提交到oj.ecustacm.cn，都是“答案錯誤”，因為這是個填空題，沒有輸入，只有輸出，可以自己運行得到答案后，提交到OJ時，直接列印答案就行了，）

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x;
    int y;
    string p;  //path,記錄從起點(0,0)到這個點(x,y)的完整路徑
};
char a[31][51];  //存地圖

char k[4]={'D','L','R','U'};
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
int vis[30][50];  //標記，vis=1: 已經搜過，不用再搜
void bfs(){
    node start; start.x=0;  start.y=0;   start.p="";  //定義起點
    vis[0][0]=1;              //標記起點被搜過

    queue<node>q;   q.push(start);   //把第一個點放進佇列，開始BFS
    while(!q.empty()){
        node now = q.front();  //取出隊首
        q.pop();
        if(now.x==29 && now.y==49){ //第一次達到終點，這就是字典序最小的最短路徑
            cout<<now.p<<endl;       //列印路徑：從(0,0)到(29,49)
            return;
        }
        for(int i=0;i<4;i++){  //擴散鄰居結點
            node next;
            next.x = now.x+dir[i][0];
            next.y = now.y+dir[i][1];
            if(next.x<0||next.x>=30||next.y<0||next.y>=50)  //越界了
                continue;
            if(vis[next.x][next.y]==1||a[next.x][next.y]=='1')  //vis=1:已經搜過;  a=1:是障礙
                continue;
            vis[next.x][next.y]=1;  //標記被搜過
            next.p = now.p+k[i];  //記錄完整路徑：把上一個點的路徑，加上這一步后，復制給下一個點
            q.push(next);
        }
    }
}
int main(){
    for(int i=0;i<30;i++)  cin>>a[i];  //讀題目給的地圖資料
    bfs();
}

3.2 標準方法

?? 注意看print_path()，它是遞回函式，先遞回再列印，從終點開始，回溯到起點后，再按從起點到終點的順序，正序列印出完整路徑，

//User: 19031010128
#include<bits/stdc++.h>
using namespace std;
struct node{
    int x;
    int y;
};
char a[31][51];  //存地圖

char k[4]={'D','L','R','U'};
int dir[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
int vis[30][50];  //1:已經搜過，不用再搜

char pre[31][51]; //用于查找前驅點，例如pre[x][y] = ‘D’，表示上一個點往下走一步到了(x,y)，那么上一個點是(x-1,y)
void print_path(int x,int y){      //列印路徑：從(0,0)到(29,49)
  if(x==0 && y==0)   //回溯到了起點，遞回結束，回傳
     return;
  if(pre[x][y]=='D')  print_path(x-1,y);   //回溯，往上 U
  if(pre[x][y]=='L')  print_path(x,  y+1); //回溯，往右 R
  if(pre[x][y]=='R')  print_path(x,  y-1);
  if(pre[x][y]=='U')  print_path(x+1,y);
  printf("%c",pre[x][y]);                  //最后列印的是終點
}

void bfs(){
    node now,next;
    queue<node>q;
    now.x=0;
    now.y=0;
    vis[0][0]=1;
    q.push(now);

    while(!q.empty()){
        now=q.front();
        q.pop();
        if(now.x==29 && now.y==49){ //第一次達到終點，這就是字典序最小的最短路徑
            print_path(29,49);      //列印路徑，從終點回溯到起點，但是列印出來是從起點到終點的正序
            return;
        }
        for(int i=0;i<4;i++){
            next.x = now.x+dir[i][0];
            next.y = now.y+dir[i][1];
             if(next.x<0||next.x>=30||next.y<0||next.y>=50)  //越界
                continue;
            if(vis[next.x][next.y]==1||a[next.x][next.y]=='1')  //vis=1:已經搜過;  a=1,是障礙
                continue;
            vis[next.x][next.y]=1;
            pre[next.x][next.y] = k[i];   //記錄點(x,y)的前驅
            q.push(next);
        }
    }
}
int main(){
    for(int i=0;i<30;i++)  cin>>a[i];  //讀題目給的地圖資料，30行，每行50個
    bfs();
}