题目描述

一个 $N$ 行 $N$ 列的地图， . 代表一个空的宿舍，# 代表一个障碍物，P 代表一个人正在这个宿舍中，地图中有且只有 $2$ 人。

你可以选择让这 $2$ 个人 同时 向上下左右中的一个方向移动，若一个人移动后走到了边界外或者障碍物上，他就不会移动。

问最少要移动几次，可以把这 $2$ 个人移动到同一个宿舍中。若不可能移动到同一个宿舍，输出 -1。

输入格式

第一行输入 $N$

接下来输入一个 $N\times N$ 的字符矩阵。

输出格式

根据题目要求输出对应的内容。

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

3

2
P#
#P

-1

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

10

提示

数据范围

• $N$ 是一个介于 $2$ 和 $60$ 之间的整数，包括首尾两个整数。
• $S_i$ 是长度为 $N$ 的字符串，由 P、. 和 # 组成。
• 在 $(i, j)$ 中， $S_i$ 的第 $j$ 个字符是 P 的字符串正好有两对。

Sample Explanation 1

我们称从 $(3, 2)$ 开始的玩家为玩家 $1$ 和从 $(4, 3)$ 开始的玩家棋手 $2$。

例如，按照下面的下法，两位棋手可以在三步之内下到同一格：

• 选择向左。棋手 $1$ 移动到 $(3, 1)$ ，棋手 $2$ 移动到 $(4, 2)$ 。
• 选择向上。棋手 $1$ 不动，棋手 $2$ 移动到 $(3, 2)$ 。
• 选择向左。棋手 $1$ 不动，棋手 $2$ 移动到 $(3, 1)$ 。