原题链接:D - Synchronized Players (atcoder.jp)
题目翻译:一个n行n列的地图,.代表一个空的宿舍,#代表一个障碍物,P代表一个人正在这个宿舍中,地图中有且只有2人。你可以选择让这2个人同时向上下左右中的一个方向移动,若一个人移动后走到了边界外或者障碍物上,他就不会移动。问最多要移动几次,可以把这2个人移动到同一个宿舍中。若不可能移动到同一个宿舍,输出-1。
n的范围是[2,60]
思路:就是对二个人同时bfs,如果有障碍物或者超出边界就不动,当二个人相遇的时候就更新最小值,因为bfs是一层一层搜索所以第一次搜索到就是最小值。因为这一题是要二个人同时动,并且还要会和在同一点,所以记录是否走过的数组要开四维的,分别是第一个人的坐标和第二个人的坐标。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10;
char mp[1010][1010];
bool st[70][70][70][70];
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
struct node
{
ll x,y,a,b,step;
};
int main()
{
ios::sync_with_stdio(NULL);
cin.tie(0),cout.tie(0);
ll n;cin>>n;
queue<node> op;
ll x=0,y=0,z,v;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>mp[i][j];
if(mp[i][j]=='P')
{
if(!y||!x)x=i,y=j;
else z=i,v=j;
}
}
}
op.push({x,y,z,v,0});
ll ans=1e18;
while(op.size())
{
auto k=op.front();
op.pop();
x=k.x,y=k.y,z=k.a,v=k.b;
ll k1=k.step;
if(st[x][y][z][v])continue;
st[x][y][z][v]=1;
if(x==z&&y==v)
{
ans=min(ans,k1);
break;
}
for(int i=0;i<4;i++)
{
ll px=x+dx[i],py=y+dy[i],pz=z+dx[i],pv=v+dy[i];
if(px<1||px>n||py>n||py<1||mp[px][py]=='#')px=x,py=y;
if(pz<1||pz>n||pv>n||pv<1||mp[pz][pv]=='#')pz=z,pv=v;
op.push({px,py,pz,pv,k1+1});
}
}
if(ans!=1e18)cout<<ans;
else cout<<-1;
return 0;
}