# Untitled

unknown
plain_text
17 days ago
1.8 kB
0
Indexable
Never
```#define ll long long
#define pb push_back
#define ipar(arr, n, dt) vector<dt> arr(n); for(int i=0;i<n;i++) cin>>arr[i];
#include <cmath>
#include <bits/stdc++.h>
#include <queue>
using namespace std;

bool isvalid(ll x,ll y,ll n){
return (x>=0 && x<n && y>=0 && y<n);
}

void solve(){
ll n; cin>>n;
ll res=-1;
queue<array<ll,5>> q;
vector<array<ll,2>>p;
bool vis[61][61][61][61]={false};

vector<vector<char>>grid(n,vector<char>(n));
for(int i=0;i<n;i++){
string s;
cin>>s;
for(int j=0;j<n;j++){
grid[i][j]=s[j];
if(grid[i][j]=='P') p.push_back({i,j});
}
}
q.push({p[0][0],p[0][1],p[1][0],p[1][1],0}); //coordinates ,dist

while(!q.empty()){
array <ll,5> front=q.front();
array<ll,2> p1={front[0],front[1]}, p2={front[2],front[3]};
q.pop();
if(p1==p2){
res=front[4];
break;
}

vector<pair<ll,ll>> dir={{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

for(auto d:dir){
array<ll,2> np1=p1,np2=p2;

if( isvalid(p1[0]+d.first,p1[1]+d.second,n) && grid[p1[0]+d.first][p1[1]+d.second]!='#'){
np1={p1[0]+d.first,p1[1]+d.second};

}

if(isvalid(p2[0]+d.first,p2[1]+d.second,n) && grid[p2[0]+d.first][p2[1]+d.second]!='#'){
np2={p2[0]+d.first,p2[1]+d.second};
}

if(vis[np1[0]][np1[1]][np2[0]][np2[1]]==0){
q.push({np1[0],np1[1],np2[0],np2[1],front[4]+1});
vis[np1[0]][np1[1]][np2[0]][np2[1]]=1;
}
}
}
cout<<res<<"\n";
}

signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;

while(t--) solve();
}

// &&  && ){```