题目描述

有一个 $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$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5
....#
#..#.
.P...
..P..
....#

输出 #1

3

输入输出样例 #2

输入 #2

2
P#
#P

输出 #2

-1

输入输出样例 #3

输入 #3

10
..........
..........
..........
..........
....P.....
.....P....
..........
..........
..........
..........

输出 #3

10

说明/提示

限制条件

• $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 翻译