倪文迪陪你学藍橋杯2021冬休み毎日一題:1.26日(2019省試合A組第4題)

2021年冬休み毎日1題、2017~2019年の省試合本題.本文の内容は倪文迪(華東理工大学コンピュータ学部ソフトウェア192クラス)と羅勇軍先生から提供された.毎日1題、ブルーブリッジカップコラムに注目:https://blog.csdn.net/weixin_43914593/category_10721247.html
C++、Java、Pythonの3言語のコードを提供します.
文書ディレクトリ

1、題名説明

2、題解

3、2種類のパス印刷方法

3.1簡単な方法

3.2標準方法

2019省試合A組第4題「迷宮」、タイトルリンク:http://oj.ecustacm.cn/problem.php?id=1455
この問題は初心者の訓練のいい問題だ.
1、テーマの説明
次の図は、1とマークされた障害物、0とマークされた通行可能な場所を示す迷路の平面図です.010000,000,000,100,001,110,000迷宮の入り口は左上角、出口は右下角で、迷宮の中で、1つの位置からこの上、下、左、右の4つの方向の1つしか歩けません.上の迷路については、入口からDRRURRDDDRの順に迷路を通過することができ、全部で10歩です.このうちD,U,L,Rはそれぞれ下,上,左,右を表す.次のようなより複雑な迷路(30行50列)については、迷路を通過する方法を見つけてください.使用するステップ数が最も少なく、ステップ数が最も少ない前提の下で、辞書の順序が最も小さいものを答えとして見つけてください.辞書順ではD
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/104608578BFSの特徴は、層ごとに拡散している(BFSのキューに隣接ノードを入れる場合は、始点から遠近の順に入れる:始点から1の隣接ノードを先に入れ、加えた後、距離2の隣接ノードを加えるなど)、1層を検索してから、次の層を検索し続けることです.1つの経路は起点から始まり、各層に沿って徐々に外に進み、各層ごとに経路長が1増加する.では、同じ長さの最短パスはすべて同じ階層から拡散されます.最初の到達点の最短パスを検索した後、検索を続行すると、他の最短パスではない可能性があります.  (4)題は辞書順の最小の最短経路を返すことを要求するが,次の層(BFSのキューに次の層のノードを加える)を拡散するたびに辞書順"D  であるため,本題は基本的なBFS探索最短経路である.複雑度はO(n)O(n)O(n)O(n),n n n nは迷宮内のノードの総数であり,本題は30である.× 50 = 1500 30\times 50=1500 30×50=1500個のポイントです.各ポイントは1回しか検索できないため、キューに入ることとキューを出ることができます.
3、2種類のパス印刷方法
  パスはどのように印刷しますか?簡単な方法は、1つの点v vに拡張するたびに、始点s s sからv v vまでの完全なパスp a t h pathがv v v vに格納されます.終点t t tに到達すると、始点s sからt t t tまでの完全なパスが得られます.このような欠点は、各点に完全なパスが格納されているため、多くの空間を占有することです. ノードに完全なパスを格納する必要はありません.各ポイントに前駆ノードを記録すれば十分です.これにより、終点から始点に一歩一歩遡り、完全なパスが得られます(詳細は「アルゴリズムコンテスト入門から進級」245ページ「最短パスの印刷」を参照).このパス記録方法を「標準方法」と呼びます.を選択します.
3.1簡単な方法
確かに簡単で、ゴール後、cout< 。
  （ ， 2 ， oj.ecustacm.cn， “ ”， ， ， 。 ， OJ ， 。）で

#include
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
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();
}