广度优先搜索算法的思想主要是将每种状态用队列储存起来,再对每种状态进行拓展,例如说对于(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];//记录父节点,以及当前节点是往哪里走的
        }
    }
}