A5442 | $午枫的双向奔赴2$

时间限制2s

内存限制256MB

通过 / 提交0/0

题目描述

有一个 $n$ 行 $n$ 列的方格迷宫，每个格子要么是空地，要么是有障碍物的格子。方格迷宫中第 $i$ 行第 $j$ 列的格子记作 $(i, j)$。 小午和小枫分别站在两个不同的空地上。第 $i$ 行第 $j$ 列的格子的情况通过一个字符 $s_{i,j}$ 给出，具体如下： - 如果 $s_{i,j}$ 是 P，则 $(i, j)$ 是空地，并且小午和小枫其中一人在这个格子。 - 如果 $s_{i,j}$ 是 .，则 $(i, j)$ 是空地。 - 如果 $s_{i,j}$ 是 #，则 $(i, j)$ 是有障碍物的格子。 这个迷宫中小午和小枫被施加了束缚魔法，此魔法的效果是： 两个人需要同时选择同一个方向（上、下、左、右），之后两人都会尝试向该方向移动一格。如果移动后的格子存在是空地，则移动过去，否则原地不动。 请你求出，为了让小午和小枫通过反复移动最终汇合到同一个格子，所需的最小移动次数。如果无论如何都无法让他们汇合，则输出 $-1$。

第一行输入一个整数 $n$ $(2\leq n\leq 60)$ ，表示方格的大小。 接下来输入 $n$ 行，每行 $n$ 个字符 $s_{i,j}$ $(s_{i,j}\in \{$ P ，. ，# $\})$ ，表示第 $i$ 行第 $j$ 列的情况。保证 P 恰好有 $2$ 个。

输出一个整数，表示小午和小枫汇合的最小移动次数。

输入 #1

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

输出 #1

C++ 编辑器

输入

输出