AtCoder Beginner Contest 339D問題

解法

2人のプレイヤーの座標の組を頂点にもつグラフ上でBFS．

実装

移動先の位置は，今のマスにも依存することに注意． 壁に向かって移動しようとしたときは，今の位置にとどまるが， もう一方のプレイヤーが移動できる場合がある．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

ll dis[65][65][65][65];

ll vis[65][65][65][65];

int main() {

  ll n;

  cin >> n;

  vector<string> s(n); cinv(s);

  auto valid = [&](ll& x) -> void {

    chmin(x, n-1);

    chmax(x, 0LL);

  };

  queue<vll> q;

  auto push = [&](ll d, ll x0, ll y0, ll x1, ll y1) -> void {

    if(vis[x0][y0][x1][y1]) return;

    vis[x0][y0][x1][y1] = true;

    dis[x0][y0][x1][y1] = d;

    q.push({x0,y0,x1,y1});

  };

  vll tmp;

  rep(x,n) rep(y,n){

    if(s[x][y] == 'P') tmp.push_back(x), tmp.push_back(y);

  }

  push(0, tmp[0], tmp[1], tmp[2], tmp[3]);

  while(q.size()){

    vll cu = q.front(); q.pop();

    ll x0 = cu[0];

    ll y0 = cu[1];

    ll x1 = cu[2];

    ll y1 = cu[3];

    ll cd = dis[x0][y0][x1][y1];

    vll dx = {1,0,-1,0};

    vll dy = {0,1,0,-1};

    rep(i,4) {

      ll nx0 = x0 + dx[i];

      ll nx1 = x1 + dx[i];

      ll ny0 = y0 + dy[i];

      ll ny1 = y1 + dy[i];

      valid(nx0);

      valid(ny0);

      valid(nx1);

      valid(ny1);

      if(s[nx0][ny0] == '#') nx0 = x0, ny0 = y0;

      if(s[nx1][ny1] == '#') nx1 = x1, ny1 = y1;

      push(cd + 1, nx0, ny0, nx1, ny1);

    }

  }

  ll ans = INFL;

  rep(x,n) rep(y,n) if(vis[x][y][x][y]){

    chmin(ans, dis[x][y][x][y]);

  }

  if(ans >= INFL) ans = -1;

  cout << ans << endl;

  return 0;

}