Untitled

mail@pastecode.io avatar
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();
}


// &&  && ){
Leave a Comment