#P0070. 双生迷宫
双生迷宫
题目描述
给定一个 的迷宫,每格为以下三种类型之一:
:平地,可以通行;
:陷阱,进入后立即失败;
:传送门,进入后立即离开迷宫。
两个人同时从平地 出发。两人都尚未离开时,必须同步向相反方向移动:一人向上时另一人向下,一人向左时另一人向右。每人每次均移动一格。
若任意一人越界或进入陷阱,本次行动失败;即使另一人在同一步进入传送门,也不能挽救失败。一人进入传送门后立即离开,不再移动;剩下的人此后可自由选择上下左右方向,直到也进入传送门。
两人同步移动一次计为一步;一人离开后,剩余的人每移动一次也计为一步。判断能否让两人都成功离开,并求最少总步数。
输入格式
第一行输入四个整数 $n,m,x,y\left(1\leqq n,m\leqq2\times10^3;\ 1\leqq x\leqq n;\ 1\leqq y\leqq m\right)$。
此后 行,每行输入一个长度为 、仅含 、 和 的字符串。
行、列均从 开始编号,保证起点 为平地。
输出格式
输出一个整数,代表两人均离开所需的最少总步数;无法成功时输出 。
测试样例
3 3 2 2
@.@
#..
@.@
2
样例 1 解释
一人先向上、再向左到达 的传送门;另一人先向下、再向右到达 的传送门。两人同时离开,共 步。一步内无法进入传送门,因此这是最少步数。
1 3 1 2
..@
3
3 1 2 1
#
.
@
-1