题解 | #Penguins#

I 题题解

思路

广搜

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 50;

struct node{
    int x1,y1;
    int x2,y2;
    int cnt;
    char c;
}p[N][N][N][N];
char A[N][N],B[N][N];
char C[4]={'D','L','R','U'};
int rou1[4][2]={1,0,0,-1,0,1,-1,0};
int rou2[4][2]={1,0,0,1,0,-1,-1,0};

bool check1(int x,int y){
    if(x<1||x>20||y<1||y>20||A[x][y]=='#') return true;
    return false;
}

bool check2(int x,int y){
    if(x<1||x>20||y<1||y>20||B[x][y]=='#') return true;
    return false;
}

void print(){
    for(int i=1;i<=20;i++){
        for(int j=1;j<=20;j++) cout<<A[i][j];
        cout<<" ";
        for(int j=1;j<=20;j++) cout<<B[i][j];
        puts("");
    }
}

void BFS(){   
    memset(p,0x3f3f3f3f,sizeof p);
    queue<node> q;
    q.push({20,20,20,1,0});
    p[20][20][20][1].cnt=0;

    while(q.size()){
        node t=q.front();        
        q.pop();
        int x1=t.x1,y1=t.y1,x2=t.x2,y2=t.y2;
        int d=p[x1][y1][x2][y2].cnt;      

        for(int i=0;i<4;i++){
            int x11=x1+rou1[i][0],y11=y1+rou1[i][1];
            int x22=x2+rou2[i][0],y22=y2+rou2[i][1];
            char c=C[i];

            if(!check1(x11,y11)&&!check2(x22,y22)){
                if(p[x11][y11][x22][y22].cnt>d+1) {
                    p[x11][y11][x22][y22]={x1,y1,x2,y2,d+1,c}; 
                    q.push({x11,y11,x22,y22,d+1});   
                }     
            }

            else if(check1(x11,y11)&&!check2(x22,y22)){
                x11=x1,y11=y1;
                if(p[x11][y11][x22][y22].cnt>d+1) {
                    p[x11][y11][x22][y22]={x1,y1,x2,y2,d+1,c}; 
                    q.push({x11,y11,x22,y22,d+1});
                }
            }

           else if(check2(x22,y22)&&!check1(x11,y11)) {
                x22=x2,y22=y2;
                if(p[x11][y11][x22][y22].cnt>d+1){                
                  p[x11][y11][x22][y22]={x1,y1,x2,y2,d+1,c}; 
                  q.push({x11,y11,x22,y22,d+1});
                }  
            }   

        } 
    }

    cout<<p[1][20][1][1].cnt<<endl;

    string s;
    int x1=1,y1=20,x2=1,y2=1;
    while(p[x1][y1][x2][y2].cnt!=0){
        node &u=p[x1][y1][x2][y2]; 
        A[x1][y1]='A',B[x2][y2]='A';
        x1=u.x1; y1=u.y1; x2=u.x2, y2=u.y2;
        s+=u.c;
    }
    A[20][20]='A',B[20][1]='A';

    reverse(s.begin(),s.end());    cout<<s<<endl;
    print();
}

int main(){
    for(int i=1;i<=20;i++)  cin>>A[i]+1>>B[i]+1;   BFS();
    return 0;
}