Synchronized Players

题目描述

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

2
P#
#P

-1

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

10

提示

$N$ 是一个介于 $2$ 到 $60$（含）之间的整数。 $S_i$ 是一个长度为 $N$ 的由 $P$、$.$ 和 # 组成的字符串。 恰好有两个位置 $(i, j)$ 满足 $S_i$ 的第 $j$ 个字符是 $P$。我们称起始于 $(3, 2)$ 的玩家为玩家 1，起始于 $(4, 3)$ 的玩家为玩家 2。 例如，按下述操作可以在三步内将两名玩家移到同一格子：

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

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

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

标签: AtCoder|abc339D

来源

AtCoder|abc339D