← 返回题目列表

AtCoder · abc339_d

G. 同步播放器

中文机器翻译题面 查看原题

分数: 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