AT_abc339_d [ABC339D] Synchronized Players

[problemUrl]: https://atcoder.jp/contests/abc339/tasks/abc339_d $ N $ 行 $ N $ 列のグリッドがあり、各マスは空きマスか障害物のあるマスのいずれかです。グリッドの上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,\ j) $ と表記します。 また、$ 2 $ 人のプレイヤーがグリッド上の相異なる空きマス上におり、各マスの情報は $ N $ 個の長さ $ N $ の文字列 $ S_1,\ S_2,\ \ldots,\ S_N $ として以下の形式で与えられます。 - $ S_i $ の $ j $ 文字目が `P` であるとき、$ (i,\ j) $ は空きマスであり、プレイヤーがいる - $ S_i $ の $ j $ 文字目が `.` であるとき、$ (i,\ j) $ は空きマスであり、プレイヤーがいない - $ S_i $ の $ j $ 文字目が `#` であるとき、$ (i,\ j) $ は障害物のあるマスである 以下の操作を繰り返し $ 2 $ 人のプレイヤーを同じマスに集めるために必要な操作回数の最小値を求めてください。ただし、操作の繰り返しにより $ 2 $ 人のプレイヤーを同じマスに集めることができない場合には `-1` を出力してください。 - 上下左右のいずれかの方向を決める。そして各プレイヤーはともにその方向に隣接するマスへの移動を試みる。各プレイヤーは移動先のマスが存在し、かつ空きマスであるならば移動し、そうでないならば移動しない。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ $ \vdots $ $ S_N $

答えを出力せよ。

### 制約 - $ N $ は $ 2 $ 以上 $ 60 $ 以下の整数 - $ S_i $ は長さ $ N $ の `P`, `.`, `#` からなる文字列 - $ S_i $ の $ j $ 文字目が `P` であるような組 $ (i,\ j) $ の個数はちょうど $ 2 $ つ ### Sample Explanation 1 はじめに $ (3,\ 2) $ にいるプレイヤーをプレイヤー $ 1 $、$ (4,\ 3) $ にいるプレイヤーをプレイヤー $ 2 $ とします。 例えば以下のようにすることで、$ 3 $ 回の操作で $ 2 $ 人のプレイヤーが同じマスに集まります。 - 左を選択する。プレイヤー $ 1 $ は $ (3,\ 1) $ に移動し、プレイヤー $ 2 $ は $ (4,\ 2) $ に移動する。 - 上を選択する。プレイヤー $ 1 $ は移動せず、プレイヤー $ 2 $ は $ (3,\ 2) $ に移動する。 - 左を選択する。プレイヤー $ 1 $ は移動せず、プレイヤー $ 2 $ は $ (3,\ 1) $ に移動する。