← 返回题目列表

AtCoder · abc400_d

G. 高桥破墙者

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

分数: 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