A5400 · Takahashi the Wall Breaker

题目描述

高桥君想去鱼店买鳗鱼。 高桥君居住的城镇由 $H$ 行 $W$ 列的网格状区域构成，每个区域是道路或墙壁。 以下，将从上往下第 $i$ 行（$1 \leq i \leq H$）、从左往右第 $j$ 列（$1 \leq j \leq W$）的区域表示为区域 $(i, j)$。 各区域的信息由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2, \ldots, S_H$ 给出。具体来说，当 $S_i$ 的第 $j$ 个字符（$1 \leq i \leq H$，$1 \leq j \leq W$）为 . 时，区域 $(i, j)$ 是道路；当为 # 时，区域 $(i, j)$ 是墙壁。 高桥君可以按任意顺序重复执行以下两种操作： - 移动到上下左右相邻的、位于城镇内且为道路的区域。 - 选择一个上下左右方向，进行**前踢**。 当高桥君进行前踢时，可以将当前区域在该方向上 **前 1 格** 和 **前 2 格** 的区域（如果它们是墙壁）变为道路。 注意：即使前 1 格或前 2 格位于城镇外，仍然可以进行前踢操作，但城镇外的区域不会发生变化。 高桥君最初位于区域 $(A, B)$，想要到达位于区域 $(C, D)$ 的鱼店。 保证高桥君初始所在的区域及鱼店所在的区域是道路。 请计算高桥君到达鱼店所需的最小**前踢次数**。

输入格式

第一行输入两个正整数 $H$，$W$ 接下来$H$行，每行一个长度为$W$的字符串 最后一行输入四个数字 $A$ , $B$ , $C$ , $D$

输出格式

输出高桥君到达鱼店所需的最小**前踢次数**。

输入输出样例

输入 #1

10 10
..........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
.##.#.#.#.
###.#.#.#.
###.#.#.#.
#.....#...
1 1 7 1

输出 #1

输入 #2

2 2
.#
#.
1 1 2 2

输出 #2

输入 #3

1 3
.#.
1 1 1 3

输出 #3

输入 #4

20 20
####################
##...##....###...###
#.....#.....#.....##
#..#..#..#..#..#..##
#..#..#....##..#####
#.....#.....#..#####
#.....#..#..#..#..##
#..#..#.....#.....##
#..#..#....###...###
####################
####################
##..#..##...###...##
##..#..#.....#.....#
##..#..#..#..#..#..#
##..#..#..#..#..#..#
##.....#..#..#..#..#
###....#..#..#..#..#
#####..#.....#.....#
#####..##...###...##
####################
3 3 18 18

输出 #4

A5400 | Takahashi the Wall Breaker

题目描述

输入格式

输出格式

输入输出样例

A5400 | $Takahashi the Wall Breaker$