AT_abc339_d [ABC339D] Synchronized Players

有一个 $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)$ 是有障碍物的格子。 请你求出，为了让两名玩家通过以下操作反复移动最终汇合到同一个格子，所需的最小操作次数。如果无论如何都无法让两名玩家汇合，则输出 $-1$。 每次操作如下： - 选择一个方向（上、下、左、右）后，两名玩家都尝试向该方向移动一格。如果移动后的格子存在且是空地，则玩家移动过去，否则原地不动。

输入按以下格式从标准输入读入。 > $N$ > $S_1$ > $S_2$ > $\vdots$ > $S_N$

请输出答案。

### 限制条件 - $N$ 是 $2$ 到 $60$ 之间的整数。 - $S_i$ 是由 `P`、`.`、`#` 组成的长度为 $N$ 的字符串。 - 所有 $S_i$ 的字符中，`P` 出现的格子恰好有 $2$ 个。 ### 样例解释 1 假设最开始在 $(3, 2)$ 的玩家为玩家 $1$，在 $(4, 3)$ 的玩家为玩家 $2$。例如，可以按如下方式用 $3$ 次操作让两名玩家汇合： - 选择左方向。玩家 $1$ 移动到 $(3, 1)$，玩家 $2$ 移动到 $(4, 2)$。 - 选择上方向。玩家 $1$ 不动，玩家 $2$ 移动到 $(3, 2)$。 - 选择左方向。玩家 $1$ 不动，玩家 $2$ 移动到 $(3, 1)$。 由 ChatGPT 4.1 翻译