ACM中的AC题_

$\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$ 。

$\hspace{15pt}$ 输入包含 $n+1$ 行：
$\hspace{23pt}\bullet\,$ 第一行输入四个整数 $n,m,x,y\left(1\leqq n,m\leqq 2\times10^{3};\ 1\leqq x\leqq n;\ 1\leqq y\leqq m\right)$ ；
$\hspace{23pt}\bullet\,$ 接下来 $n$ 行，第 $i$ 行输入一个长度为 $m$ 的字符串 $s_i$ ，仅由 `.`、`#`、`@` 组成，描述第 $i$ 行的地形。
$\hspace{15pt}$ 保证起点 $(x,y)$ 处为平地。

ACM中的AC题

输入描述:

输出描述:

输入

输出

说明

输入

输出

输入

输出

说明

备注:

问题信息

热门推荐

相关试题