#P0070. 双生迷宫

双生迷宫

题目描述

\hspace{15pt}给定一个 n×mn\times m 的迷宫,每格为以下三种类型之一:

∙ \hspace{23pt}\bullet\,‘.’\texttt{`.'}:平地,可以通行;

∙ \hspace{23pt}\bullet\,‘#’\texttt{`\#'}:陷阱,进入后立即失败;

∙ \hspace{23pt}\bullet\,‘@’\texttt{`@'}:传送门,进入后立即离开迷宫。

\hspace{15pt}两个人同时从平地 (x,y)(x,y) 出发。两人都尚未离开时,必须同步向相反方向移动:一人向上时另一人向下,一人向左时另一人向右。每人每次均移动一格。

\hspace{15pt}若任意一人越界或进入陷阱,本次行动失败;即使另一人在同一步进入传送门,也不能挽救失败。一人进入传送门后立即离开,不再移动;剩下的人此后可自由选择上下左右方向,直到也进入传送门。

\hspace{15pt}两人同步移动一次计为一步;一人离开后,剩余的人每移动一次也计为一步。判断能否让两人都成功离开,并求最少总步数。

输入格式

\hspace{15pt}第一行输入四个整数 $n,m,x,y\left(1\leqq n,m\leqq2\times10^3;\ 1\leqq x\leqq n;\ 1\leqq y\leqq m\right)$。

\hspace{15pt}此后 nn 行,每行输入一个长度为 mm、仅含 ‘.’\texttt{`.'}、‘#’\texttt{`\#'} 和 ‘@’\texttt{`@'} 的字符串。

\hspace{15pt}行、列均从 11 开始编号,保证起点 (x,y)(x,y) 为平地。

输出格式

\hspace{15pt}输出一个整数,代表两人均离开所需的最少总步数;无法成功时输出 −1-1。

测试样例

3 3 2 2
@.@
#..
@.@
2

样例 1 解释

\hspace{15pt}一人先向上、再向左到达 (1,1)(1,1) 的传送门;另一人先向下、再向右到达 (3,3)(3,3) 的传送门。两人同时离开,共 22 步。一步内无法进入传送门,因此这是最少步数。

1 3 1 2
..@
3
3 1 2 1
#
.
@
-1