ACM中的AC题
题号：NC276118
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

众所周知，出题人没玩过双人成行，所以出了这道题
你一觉醒来，发现你和另一个时空的你被困在 n*m 大小矩形孤岛的 (x, y) 地块上
在地图中最多包含 平地，陷阱和传送门 三种不同地块
你和另外一个时空的你都可以上下左右移动到相邻的地块中
可是你和外一个时空的你只能同时以相反的方向移动
两人均不能跨过边界，即到达孤岛外的地方；任意人到达陷阱处会立刻死亡

现在，你能否给出一个移动序列，使得两人均能从传送门离开，其中任意一人到达传送门后一定会离开且不会再回到该孤岛中;
如果有，请输出该序列的最短长度、反之输出 -1

输入描述:

第一行四个正整数 n, m, x, y
接下来 n 行，每行一个长度为 m 的字符串

1\le n,m\le 2× 10^3; ~1\le x\le n; ~1\le y\le m
数据保证
字符串仅包含 .#@ 三种字符 .(平地) #(陷阱) @(传送门)
保证 (x, y) 位置是平地.

输出描述:

输出一个整数
若能离开，请请输出该序列的最短长度
反之输出 -1
示例1

输入

复制 
3 3 2 2
@.@
#..
@.@

输出

复制 
2

说明

你可以先往上后往左到达(1,1)传送门
另外一个时空的你会先下后右到达(3,3)传送门
示例2

输入

复制 
1 3 1 2
..@

输出

复制 
3
示例3

输入

复制 
3 1 2 1
#
.
@

输出

复制 
-1

说明

显然，谁都不想走到陷阱那 ...

备注:

本题输入较大，建议使用较快语言和较快的输入