官方题解

题目大意

有两个人位于不同的起点，每次移动两人只能往同一方向移动，如果在边界或移动方向有障碍物则不移动，求两人移动到同一点的最短时长。

解题思路

考虑到两个人第一次到达某个位置时，花费的时间最短，不妨设其中一人的位置为 $(x_1,y_1)$ ，另一人的位置为 $(x_2,y_2)$ 。

令 $d[x_1][y_1][x_2][y_2]$ 为一人到达 $(x_1,y_1)$ ，另一人到达 $(x_2,y_2)$ 花费的最短时间。因为每次移动只花费 $1$ 单位时间，所以通过 $bfs$ 即可实现。

时间复杂度 $O(n^4)$

参考代码

#include <bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
const int N = 65;
const int INF = 1e9+10;

int n;
char g[N][N];
PII p1={-1,-1},p2={-1,-1};
int d[N][N][N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void bfs(){
    memset(d,-1,sizeof d);
    queue<pair<PII,PII>>q;
    q.push({p1,p2});
    d[p1.fi][p1.se][p2.fi][p2.se]=0;
    int ans=INF;
    
    while(!q.empty()){
        auto t=q.front();q.pop();
        p1=t.fi;
        p2=t.se;
        if(p1==p2) ans=min(ans,d[p1.fi][p1.se][p2.fi][p2.se]);
        
        for(int i=0;i<4;i++){
            int x1=p1.fi+dx[i],y1=p1.se+dy[i];
            int x2=p2.fi+dx[i],y2=p2.se+dy[i];
            
            if(g[x1][y1]=='#') x1=p1.fi,y1=p1.se;
            if(g[x2][y2]=='#') x2=p2.fi,y2=p2.se;
            if(d[x1][y1][x2][y2]==-1){
                d[x1][y1][x2][y2]=d[p1.fi][p1.se][p2.fi][p2.se]+1;
                q.push({{x1,y1},{x2,y2}});
            }
        }
    }
    if(ans==INF) cout<<-1<<endl;
    else cout<<ans<<endl;
}

int main(){
    cin>>n;
    for(int i=0;i<=n+1;i++){
        for(int j=0;j<=n+1;j++){
            if(i==0 || i==n+1 || j==0 || j==n+1) g[i][j]='#';
            else cin>>g[i][j];
            
            if(g[i][j]=='P'){
                if(p1.fi==-1) p1={i,j};
                else p2={i,j};
            }
        }
    }
    
    bfs();
    return 0;
}