ABC339D

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

int main(int argc, char **argv)
{
    ll n;
    cin >> n;
    vector<string> g(n);
    for (auto &s : g)
        cin >> s;
    using a2l = array<ll, 2>;
    a2l p1{-1, -1}, p2{-1, -1};
    for (ll i = 0; i < n; ++i)
        for (ll j = 0; j < n; ++j)
            if (g[i][j] == 'P')
                if (p1 == a2l{-1, -1})
                    p1 = {i, j};
                else
                    p2 = {i, j};
    using a5l = array<ll, 5>; // dist, x, y, p2x, p2y
    using a4l = array<ll, 4>;
    ll ans = LLONG_MAX;
    ll ds[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    /*
    map<a4l, ll> dist;
    mpq<a5l> q;
    q.push({0, p1[0], p1[1], p2[0], p2[1]});
    while (!q.empty()) {
        // dbg(q.top());
        auto [d, p1x, p1y, p2x, p2y] = q.top();
        if (p1x == 2 && p1y == 0)
            dbg(q.top());
        q.pop();
        auto p1 = a4l{p1x, p1y, p2x, p2y};
        if (dist.count(p1) != 0 && dist[p1] < d)
            continue;
        dist[p1] = d;
        if (p1x == p2x && p1y == p2y)
            ans = min(ans, d);

        for (ll i = 0; i < 4; ++i) {
            ll dx = ds[i][0], dy = ds[i][1];
            ll n1x = min(max(p1x + dx, 0ll), n - 1), n2x = min(max(p2x + dx, 0ll), n - 1);
            ll n1y = min(max(p1y + dy, 0ll), n - 1), n2y = min(max(p2y + dy, 0ll), n - 1);
            if (g[n1x][n1y] == '#')
                n1x = p1x, n1y = p1y;
            if (g[n2x][n2y] == '#')
                n2x = p2x, n2y = p2y;
            auto p2 = a4l{n1x, n1y, n2x, n2y};
            if (p1 == p2)
                continue;

            if (dist.count(p2) == 0 || dist[p2] > d + 1) {
                dist[p2] = d + 1;
                q.push({d + 1, n1x, n1y, n2x, n2y});
            }
        }
    }
    */
    using vb = vector<bool>;
    using vvb = vector<vb>;
    using vvvb = vector<vvb>;
    using vvvvb = vector<vvvb>;
    vvvvb inqueue(n, vvvb(n, vvb(n, vb(n))));
    queue<a5l> q;
    q.push({0, p1[0], p1[1], p2[0], p2[1]});
    while (!q.empty()) {
        auto [d, p1x, p1y, p2x, p2y] = q.front();
        q.pop();
        auto p1 = a4l{p1x, p1y, p2x, p2y};
        if (p1x == p2x && p1y == p2y)
            ans = min(ans, d);
        for (ll i = 0; i < 4; ++i) {
            ll dx = ds[i][0], dy = ds[i][1];
            ll n1x = min(max(p1x + dx, 0ll), n - 1), n2x = min(max(p2x + dx, 0ll), n - 1);
            ll n1y = min(max(p1y + dy, 0ll), n - 1), n2y = min(max(p2y + dy, 0ll), n - 1);
            if (g[n1x][n1y] == '#')
                n1x = p1x, n1y = p1y;
            if (g[n2x][n2y] == '#')
                n2x = p2x, n2y = p2y;
            auto p2 = a4l{n1x, n1y, n2x, n2y};
            if (p1 == p2)
                continue;
            if (inqueue[n1x][n1y][n2x][n2y] == false) {
                inqueue[n1x][n1y][n2x][n2y] = true;
                q.push({d + 1, n1x, n1y, n2x, n2y});
            }
        }
    }
    cout << (ans == LLONG_MAX ? -1 : ans) << endl;
    return 0;
};