← 返回题目列表

AtCoder · typical90_aq

043. 睡眠不足的迷宫挑战(★4)

中文机器翻译题面 查看原题

配点: 4 点

問題文

縦 H 方形,水平 W 有一个格子状的迷宫,从上方开始 i 行/从左起 j 选择列中的方块。 当表示为 (i,j) 记为。 (i,j) 是 您也可以写 S_{i,j} = # 在墙上时,S_{i,j} = . 的时候不是墙。

你想通过不断移动到上下左右相邻且不是墙的格子,移动到格子 (r_s,c_s) 到 (r_t,c_t) 。但是,如果移动方向变化的次数过多,大脑会感到疲劳,因此不太理想。此外,不允许移动到迷宫外。

请找出移动方向改变次数的最小值。

制約

  • 2 \leq H,W \leq 1000
  • 1 \leq r_s,r_t \leq H
  • 1 \leq c_s,c_t \leq W
  • (r_s,c_s) \ne (r_t,c_t)
  • H,W,r_s,c_s,r_t,c_t 是一个整数
  • S_{i,j} 是 您也可以写 # 或 至少 .
  • S_{r_s,c_s},S_{r_t,c_t} 是 您也可以写 .
  • 质量 从 (r_s,c_s) 到 (r_t,c_t) 可以移动到

入力

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

H W
r_s c_s
r_t c_t
S_{1,1} S_{1,2} ... S_{1,W}
 \vdots 
S_{H,1} S_{H,2} ... S_{H,W}

出力

请打印答案。 到达


入力例 1

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

出力例 1

2

沿最短路径前进时,在格子 (1,2) 和正方形 看看 (3,2) 处方向会改变。


入力例 2

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

出力例 2

0

入力例 3

4 6
2 1
1 5
...#..
.#.##.
.#....
...##.

出力例 3

5