← 返回题目列表

AtCoder · pakencamp_2020_day1_i

I. 弯弯曲曲

中文机器翻译题面 查看原题
配点 : 400 点

問題文

縦 H 方形,水平 W 鳟鱼 H×W 有一个由正方形组成的迷宫。 从上面 i 行,从左 j 柱方 (i,\ j) 是 可以表示为S_{i,j} 是 在 # 是墙时,. 是道路。

质量 从 (sx,\ sy) 有一条鳗鱼和一条鳟鱼 正在尝试移至 (gx,\ gy) 。 鳗鱼是 通过移动 1 次,您可以移动到与您当前所在方块相邻的路径方块。此时,你无法走出迷宫。

鳗鱼喜欢扭动。因此,我们决定在玩迷宫时设置以下限制。

  • i 如果您在第二步中向上或向下移动,i+1 第二次移动时,您必须向左和向右移动。
  • i 如果你在第二步中向左或向右移动,i+1 第二步,你必须上下移动。
  • 第一个动作允许您向任意方向移动。

鳗鱼必须大量食用,同时遵守这些限制。 您可以移至 (gx,\ gy) 吗? 确定是否可以移动后,如果可以,求所需的最少移动次数。


制約

  • 1\leq H,\ W\leq2000
  • 1\leq sx,\ gx\leq H
  • 1\leq sy,\ gy\leq W
  • S_{i,j} 是 您也可以写 # 或 .
  • S_{sx,sy} 和 按字典顺序比较 S_{gx,gy} 是 您也可以写 .
  • (sx,\ sy)≠(gx,\ gy)
  • H,\ W,\ sx,\ sy,\ gx,\ gy 是一个整数

入力

输入是按以下格式从标准输入给出的。

\(H\) \(W\)
\(sx\) \(sy\) \(gx\) \(gy\)
\(S_{1,1}\) \(S_{1,2}\) \(\ldots\) \(S_{1,W}\)
\(S_{2,1}\) \(S_{2,2}\) \(\ldots\) \(S_{2,W}\)
\(⋮\)
\(S_{H,1}\) \(S_{H,2}\) \(\ldots\) \(S_{H,W}\)

出力

鳗鱼是鳟鱼 如果可以移动到 (gx,\ gy) ,则设置最小移动次数,否则 请输出 -1 。 不要忘记输出末尾的换行符。 最好选择

入力例1

2 3
1 1 1 3
...
..#

出力例1

4

(1,\ 1)\ →\ (2,\ 1)\ →\ (2,\ 2)\ →\ (1,\ 2)\ →\ (1,\ 3) 。

入力例2

3 4
1 1 3 4
....
.#..
....

出力例2

-1

无论你如何移动,它都是一个质量 无法移动到 (3,\ 4) 。

入力例3

5 7
4 1 5 4
.#..#..
#....#.
...#..#
.#.....
..#..#.

出力例3

14