牛2 I

Penguins

题面：已知两只企鹅的始末位置，按照题目规则最短路并且有最小字典序。
解析：两只企鹅规定是同时行动，构造一个四维数组来表示两企鹅同时到两点的状态。然后直接bfs求出最短路径。用pre[][][][]数组来记录前驱状态，之后用爆搜终点到起始点，将经过的每个点变为'A'，再记录行动方向。
代码（要注意格式）

#include<bits/stdc++.h>
using namespace std;
struct node{
  int x1,y1,x2,y2;
};
char m1[25][25],m2[25][25];
int dx[4]={1,0,0,-1};
int dy[2][4]={0,-1,1,0,0,1,-1,0};
char op[4]={'D','L','R','U'};
int vis[25][25][25][25];
int f[25][25][25][25];
node pre[25][25][25][25];

char ans[404];
int num=0; 
queue<node> q;
void bfs(){
    memset(vis,0x3f3f3f,sizeof(vis));
    vis[20][20][20][1]=0;

    q.push({20,20,20,1});
    while(!q.empty()){
        node p=q.front();
        q.pop();
       int k=vis[p.x1][p.y1][p.x2][p.y2];
        for(int i=0;i<4;i++){
            int tx1=p.x1+dx[i],ty1=p.y1+dy[0][i];
            int tx2=p.x2+dx[i],ty2=p.y2+dy[1][i];
            if(m1[tx1][ty1]!='.') {
                tx1=p.x1;ty1=p.y1;
            }
            if(m2[tx2][ty2]!='.'){
                tx2=p.x2;ty2=p.y2;
            }
            if(k+1<vis[tx1][ty1][tx2][ty2]){
            vis[tx1][ty1][tx2][ty2]=k+1;
            pre[tx1][ty1][tx2][ty2]={p.x1,p.y1,p.x2,p.y2};
            f[tx1][ty1][tx2][ty2]=i;
            q.push({tx1,ty1,tx2,ty2});
            }
        }
    }

}
void solve(node s){
    node t=pre[s.x1][s.y1][s.x2][s.y2];

    m1[s.x1][s.y1]='A';
    m2[s.x2][s.y2]='A';
   if(s.x1==20&&s.y1==20&&s.x2==20&&s.y2==1) return ;
    solve(t);
     ans[num++]=op[f[s.x1][s.y1][s.x2][s.y2]];
    return ;
}
int main(){
    for(int i=1;i<=20;i++)
        scanf("%s%s",m1[i]+1,m2[i]+1);
    bfs();
    solve({1,20,1,1});
    printf("%d\n%s\n",num,ans);
     for(int i=1;i<=20;i++)
        printf("%s %s\n",m1[i]+1,m2[i]+1);

}