配点: 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