同步玩家

题目描述

有一个 $N \times N$ 的网格，每个格子要么是空的，要么包含障碍物。记 $(i, j)$ 为从上数第 $i$ 行、从左数第 $j$ 列的格子。

网格中有两个玩家，位于不同的空格子上。关于每个格子的信息以 $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$

输出格式

输出答案。

样例

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

3

记从 $(3, 2)$ 出发的玩家为玩家 1，从 $(4, 3)$ 出发的玩家为玩家 2。

例如，按如下方式操作，可以在三次移动内使两个玩家到达同一格子：

1. 选择左。玩家 1 移动到 $(3, 1)$，玩家 2 移动到 $(4, 2)$。
2. 选择上。玩家 1 不移动，玩家 2 移动到 $(3, 2)$。
3. 选择左。玩家 1 不移动，玩家 2 移动到 $(3, 1)$。

2
P#
#P

-1

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

10

数据范围

• $N$ 是 $2$ 到 $60$ 之间的整数（含端点）
• $S_i$ 是由 P、.、# 组成的长度为 $N$ 的字符串
• 恰好有两对 $(i, j)$ 使 $S_i$ 的第 $j$ 个字符为 P