5852 - 等级6:逃离迷宫

通过次数

2

提交次数

2

时间限制 : 1 秒
内存限制 : 128 MB

小A和小B被困在一个包含空地".",陷阱"#",传送阵"@"的迷宫,他们可以上下左右任意移动,但是他们的行动是相反的,即小A向上,则小B向下,问你2人都离开迷宫时,最少需要几步?注意的时其中1个人到达传送阵时,那么他就离开,另一个则还需要继续走,如果进入陷阱,代表失败,若无法离开则输出-1

输入

输入包含n+1 行:
第一行输入四个整数n,m,x,y(1≦n,m≦2×10^3 ; 1≦x≦n; 1≦y≦m);
接下来n 行,第i 行输入一个长度为m 的字符串si ,仅由 `.`、`#`、`@` 组成,描述第i 行的地形。
保证起点(x,y) 处为平地。

输出

若存在可行方案,输出最短移动步数;否则输出−1。

样例

输入

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

输出

2

输入

1 3 1 2
..@

输出

3

输入

3 1 2 1
#
.
@

输出

-1

提示

样例1 一个可以先往上后往左到达(1,1)传送门 另外一个会先下后右到达(3,3)传送门