分数: 400 点
问题陈述
有一个 N \times N 网格,其中每个单元格要么是空的,要么包含障碍物。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。
网格中不同的空单元格上还有两名玩家。每个单元格的信息如下 N 字符串 S_1, S_2, \ldots, S_N 长度 N,格式如下:
-
如果 j- 第一个字符 S_i is
P,那么 (i, j) 是一个空单元格,上面有一个玩家。 -
如果 j- 第一个字符 S_i is
.,那么 (i, j) 是一个没有玩家的空单元格。 -
如果 j- 第一个字符 S_i is
#,那么 (i, j) 包含障碍物。
通过重复以下操作,找到将两个玩家带到同一单元格所需的最小移动次数。如果通过重复操作无法将两个玩家带到同一个单元格,则打印 -1.
- 选择四个方向之一:上、下、左或右。然后,每个玩家尝试沿该方向移动到相邻的单元格。如果目标单元格存在且为空,则每个玩家都会移动,否则不会移动。
约束
- N 是介于 2 和 60,包括在内。
- S_i 是一个长度为 N 组成
P,.,和#. - 正好有两对 (i, j) 哪里 j- 第一个字符 S_i is
P.
输入
输入由标准输入按以下格式给出:
N S_1 S_2 \vdots S_N
输出
打印答案。
示例输入 1
5 ....# #..#. .P... ..P.. ....#
示例输出 1
3
让我们称玩家为 (3, 2) 玩家 1 和起始位置为 (4, 3) 玩家 2。
例如,执行以下操作可以使两个玩家通过三步移动到同一个单元格:
-
选择左侧。玩家 1 移动到 (3, 1),玩家 2 移动到 (4, 2).
-
选择。玩家 1 不移动,玩家 2 移动到 (3, 2).
-
选择左侧。玩家 1 不移动,玩家 2 移动到 (3, 1).
示例输入 2
2 P# #P
示例输出 2
-1
示例输入 3
10 .......... .......... .......... .......... ....P..... .....P.... .......... .......... .......... ..........
示例输出 3
10