分数: 400 点
问题陈述
高桥准备去鱼店买鳗鱼。
他居住的城镇被划分为一个网格 H 行和 W 列。每个单元格要么是一条路,要么是一堵墙。
让我们表示位于 i从顶部算起的第行 (1\leq i \leq H) 和 j左起第 列 (1\leq j \leq W) 作为单元格 (i,j).
有关每个单元格的信息由下式给出 H 字符串 S_1,S_2,\ldots,S_H,每个长度 W。具体来说,如果 j- 第一个字符 S_i (1\leq i \leq H,1\leq j\leq W) is .,细胞 (i,j) 是一条路;如果是的话 #,细胞 (i,j) 是一堵墙。
他可以按任意顺序重复执行以下两种类型的操作:
- 移至城镇内且为道路的相邻单元格(上、下、左或右)。
- 选择四个方向之一(上、下、左或右)并执行 前踢 朝那个方向。
当他执行前踢时,对于每个单元格最多 2 从他当前所在的牢房朝那个方向走开,如果那个牢房是墙,它就变成了路。
如果最多有一些单元格 2 几步之遥就是镇外,仍然可以进行前踢,但镇外的一切都不会改变。
他从牢房开始 (A,B),他想搬到牢房里的鱼店 (C,D).
保证他开始的单元格和有鱼店的单元格都是道路。
求最小值 前踢次数 他需要到达鱼店。
约束
- 1\leq H\leq 1000
- 1\leq W\leq 1000
- 每个 S_i 是一个长度为 W 组成
.和#. - 1\leq A,C\leq H
- 1\leq B,D\leq W
- (A,B)\neq (C,D)
- H, W, A, B, C,和 D 是整数。
- 高桥开始的小区和鱼店所在的小区都是道路。
输入
输入由标准输入按以下格式给出:
H W S_1 S_2 \vdots S_H A B C D
输出
打印高桥到达鱼店所需的最少前踢次数。
示例输入 1
10 10 .......... #########. #.......#. #..####.#. ##....#.#. #####.#.#. .##.#.#.#. ###.#.#.#. ###.#.#.#. #.....#... 1 1 7 1
示例输出 1
1
高桥在牢房中开始 (1,1).
通过反复移动到相邻的道路单元格,他可以到达单元格 (7,4).
如果他从牢房向左前踢 (7,4),细胞 (7,3) 和 (7,2) 从墙壁转向道路。
然后,继续穿过道路小区(包括已经成为道路的小区),就可以到达小区内的鱼店 (7,1).
在这种情况下,执行的前踢次数为 1,并且不执行任何前踢就不可能到达鱼店,因此打印 1.
示例输入 2
2 2 .# #. 1 1 2 2
示例输出 2
1
高桥在牢房中开始 (1,1).
当他向右执行前踢时,细胞 (1,2) 从墙变成了路。
右侧两步的单元格 (1,1) 在镇外,所以不会改变。
然后,他可以移动到单元格 (1,2) 然后到牢房里的鱼店 (2,2).
在这种情况下,执行的前踢次数为 1,并且不执行任何前踢就不可能到达鱼店,因此打印 1.
示例输入 3
1 3 .#. 1 1 1 3
示例输出 3
1
进行前踢时,如果鱼店的单元格位于可以变成道路的单元格内就可以了。具体来说,鱼店的小区从一开始就是一条路,所以保持不变;特别是,商店不会被前踢破坏。
示例输入 4
20 20 #################### ##...##....###...### #.....#.....#.....## #..#..#..#..#..#..## #..#..#....##..##### #.....#.....#..##### #.....#..#..#..#..## #..#..#.....#.....## #..#..#....###...### #################### #################### ##..#..##...###...## ##..#..#.....#.....# ##..#..#..#..#..#..# ##..#..#..#..#..#..# ##.....#..#..#..#..# ###....#..#..#..#..# #####..#.....#.....# #####..##...###...## #################### 3 3 18 18
示例输出 4
3