​时间限制​: 4秒 / ​内存限制​: 1024MB

​分数​: 400分

问题描述

有一个 N×N 的网格，其中每个格子要么是空的，要么包含一个障碍物。假设 (i,j) 表示第 i 行、第 j 列的格子。

网格上有两个玩家，它们分别位于不同的空格子上。每个格子的信息通过 N 个字符串 S₁, S₂, ..., Sₙ 给出，每个字符串的长度为 ​N​，格式如下：

• 如果 Sᵢ[j] 为 ​P​，则 (i,j) 是一个包含玩家的空格子。
• 如果 Sᵢ[j] 为 ​**.**​，则 (i,j) 是一个没有玩家的空格子。
• 如果 Sᵢ[j] 为 ​**#**​，则 (i,j) 包含一个障碍物。

现在要求找到将两个玩家移动到同一个格子的最小步数。操作是重复进行的，每次操作如下：

• 选择一个方向：上、下、左、右之一。
• 然后，每个玩家都尝试移动到相邻的格子。如果目标格子存在并且是空的，则玩家会移动，否则不移动。

如果无法将两个玩家移动到同一个格子，输出 ​**-1**​。

输入格式

输入格式如下：

N
S₁
S₂
⋮
Sₙ

• N 为网格的大小，满足 ​2 ≤ N ≤ 60​。
• 接下来的 N 行，每行包含一个长度为 N 的字符串 ​Sᵢ​，每个字符为 ​P​、. 或 ​**#**​。
• 网格中恰好有两个格子包含玩家（即恰好有两个 ​P​）。

输出格式

输出一个整数，表示将两个玩家移动到同一格子的最小步数。如果无法做到，输出 ​**-1**​。

示例输入 1

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

示例输出 1

3

示例说明

假设从 (3,2) 开始的玩家为玩家 1，从 (4,3) 开始的玩家为玩家 2。

以下操作会将两个玩家移动到同一个格子：

1. 选择左方向：玩家 1 移动到 ​**(3,1)​，玩家 2 移动到 ​(4,2)**​。
2. 选择上方向：玩家 1 不动，玩家 2 移动到 ​**(3,2)**​。
3. 选择左方向：玩家 1 不动，玩家 2 移动到 ​**(3,1)**​。

因此，最小步数为 3。

示例输入 2

2
P#
#P

示例输出 2

-1

示例输入 3

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

示例输出 3

10