演算法競賽入門Bfs演算法——路徑記錄（ penguins）

Lovely penguins is a tiny game in which the player controls two penguins.

題目鏈接

The game holds in two 20×20 grids (the left one and the right one), and each has some blocked places.We number the grid in x t h x_{th} xth?row (starting from the up), y t h y_{th} yth? column (starting from the left) {(x,y)}(x,y).

The penguins move in four directions: up, down, left, right, exactly one step once. If its way is blocked, or it reaches the border, then this movement is omitted.
The player also moves the penguins in four directions, but the behavior of the two penguins is mirrored:
L : left penguin moves to left, right penguin moves to right.
R : left penguin moves to right, right penguin moves to left.
U : both move upwards.
D : both move downwards.
An operation can be omitted on one penguin but works on another.

The left penguin starts from {(20,20)}(20,20) and wants to move to {(1,20)}(1,20).The right penguin starts from {(20,1)}(20,1) and wants to move to {(1,1)}(1,1).If both penguin reach there destination, thay win the game.
Find out the shortest way to win the game.If there are many shortest ways to win, find the one with minimum lexicographical order(D<L<R<U).
Note: When one penguin reaches the destination and the other does not, the penguin that has reached the destination may still move out of the destination.
輸入描述:
The input consists of 20 lines, each line contains 41 characters, describing the grids, separated by a space.

‘.’ means the grid is empty.

‘#’ means the grid is blocked.
輸出描述:
Output 22 lines.
The first line contains the least number of steps to win the game.
The second line contains a string consisting of ‘L’,‘R’,‘U’,‘D’, describing a way to win.
There may be many ways to win, output the one with minimum lexicographical order.
Then output 20 lines, describing the track of the two penguins, mark the track with character ‘A’, and print as input.

題目大意

有兩只企鵝分別在左下角與右下角，他們鏡像移動，請輸出字典序最小的方法，將他們二者都到達左上角與右上角的方案操作列印出來

演算法分析

廣度優先搜索演算法的思想主要是將每種狀態用佇列儲存起來,再對每種狀態進行拓展,例如說對于(20,1)這個狀態,我們依次上下左右走一步得到除了(19,1)(21,1)(20,0)(20,2)將越界和障礙物外合法進入佇列,儲存下狀態(19,1)(20,2)再依次擴展直到歷遍所有可到達點.
對于該題目我們需要做的是輸出兩只企鵝到達目的地的字典序最短路徑(下 左 右 上)的總步數與操作方法以及路徑地圖,需要注意企鵝走路是鏡像的,且可只操作一只企鵝.那么我們還需要記錄下當前狀態是由哪個狀態來轉移過來的,在輸出時使用深搜列印路徑,用語言描述總是那么蒼白下面配合代碼解釋

#include<bits/stdc++.h>
using namespace std;
const int N=25,M=2e5;
struct pg
{
    int x,y;
}p1[M],p2[M];//企鵝1 2 的位置狀態
char mp1[N][N],mp2[N][N];//企鵝1 2 的地圖
bool book[N][N][N][N];//標記已經企鵝1 2的狀態
int qu[M];//記錄父節點,即由哪個狀態轉移
int w[4][2]{1,0,0,-1,0,1,-1,0};//列舉下 左 右 上四個方向的x y陣列
char nw[5]{'D','L','R','U'},po[M];//對應的方向和記錄路徑

void dfs(int h,int t)//深搜輸出路徑
{   
    mp1[p1[h].x][p1[h].y]='A';//順便按照題目要求打上標記
    mp2[p2[h].x][p2[h].y]='A';
    if(h==1)
    {   
        cout<<t<<endl;
        return;
    }
    dfs(qu[h],t+1)
    cout<<po[h];
}

int main()
{
    for(int i=1;i<=20;i++)//讀入地圖資料
        scanf("%s%s",mp1[i]+1,mp2[i]+1);

    p1[1].x=20,p1[1].y=20,p2[1].x=20,p2[1].y=1;//初始化兩只企鵝位置
    int h=1,t=1;
    for(;h<=t;h++ )
    {
        if(p1[h].x==1&&p1[h].y==20&&p2[h].x==1&&p2[h].y==1)//如果兩只企鵝都到達目的地,說明找到一條最短路徑
        {  
            dfs(h,0);//深搜輸出路徑
            cout<<endl;
            for(int i=1;i<=20;i++)//輸出地圖
            {
                for(int j=1;j<=20;j++)
                {
                    cout<<mp1[i][j];
                }
                cout<<" ";
                 for(int j=1;j<=20;j++)
                {
                    cout<<mp2[i][j];
                }
                cout<<endl;
            }
            return 0;
        }
        for(int i=0;i<4;i++)//列舉四個方向 優先按照題目要求順序
        {   int t1x,t1y,t2x,t2y;
             t1x =p1[h].x+w[i][0];//走后坐標
             t1y=p1[h].y+w[i][1];

             t2x=p2[h].x+w[i][0];//注意鏡像,上下不變,左右相反
             t2y=p2[h].y-w[i][1];

         if(t1x<1||t1x>20||t1y<1||t1y>20||mp1[t1x][t1y]=='#')//判斷越界或者障礙
             t1x-=w[i][0],t1y-=w[i][1];
         if(t2x<1||t2x>20||t2y<1||t2y>20||mp2[t2x][t2y]=='#')
             t2x-=w[i][0],t2y+=w[i][1];

         if(book[t1x][t1y][t2x][t2y])continue;//當前狀態已經存在,跳過
          book[t1x][t1y][t2x][t2y]=1;
         t++;//新狀態儲存
         p1[t].x=t1x,p1[t].y=t1y,p2[t].x=t2x,p2[t].y=t2y;
         qu[t]=h,po[t]=nw[i];//記錄父節點,以及當前節點是往哪里走的
        }
    }
}