D-ACM中的AC题_牛客小白月赛100

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 众所周知，出题人没玩过《双人成行》，于是给出了如下经典二人协作版迷宫问题。孤岛被划分为 $n \times m$ 个方格，按行从上到下、列从左到右编号为 $(1,1)$ 至 $(n,m)$ 。地图上的地形分为三种：
$\hspace{23pt}\bullet\,$ 平地（`.`）——可以自由经过；
$\hspace{23pt}\bullet\,$ 陷阱（`#`）——踩上去立即死亡；
$\hspace{23pt}\bullet\,$ 传送门（`@`）——一旦进入便会立刻离开孤岛。

$\hspace{15pt}$ 你与来自平行时空的另一个"你"最初同时位于坐标 $(x,y)$ 的同一块平地。两人每次必须同时行动，且朝相反方向各移动一步，即：
$\hspace{23pt}\bullet\,$ 如果你选择向上，则另一个你必须向下；
$\hspace{23pt}\bullet\,$ 如果你选择向左，则另一个你必须向右，依此类推。

$\hspace{15pt}$ 在任何时刻，若有人走出边界或踏入陷阱，游戏立即失败；若有人到达传送门，则他会立刻离开并不再返回，之后剩下的那个人可以单独自由移动（不再受"相反方向"限制）。

$\hspace{15pt}$ 请判断是否存在一条合法的移动序列，使得两个人都能成功离开孤岛；若存在，请输出最短所需步数，否则输出 $-1$ 。

输入描述:

输入包含  行：
第一行输入四个整数 ；
接下来  行，第  行输入一个长度为  的字符串 ，仅由 `.`、`#`、`@` 组成，描述第  行的地形。
保证起点  处为平地。

输出描述:

若存在可行方案，输出最短移动步数；否则输出 。

示例1

输入

复制

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

输出

复制

说明

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

示例2

输入

复制

1 3 1 2
..@

输出

复制

示例3

输入

复制

3 1 2 1
#
.
@

输出

复制

-1

说明

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

题目描述

输入描述:

输出描述:

输入

输出

说明

输入

输出

输入

输出

说明

备注: