← 返回题单
题单练习 广度优先搜索
← 上一题 下一题 →

A5400 | Takahashi the Wall Breaker

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

高桥君想去鱼店买鳗鱼。

高桥君居住的城镇由 $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
1
输入 #2
2 2
.#
#.
1 1 2 2
输出 #2
1
输入 #3
1 3
.#.
1 1 1 3
输出 #3
1
输入 #4
20 20
####################
##...##....###...###
#.....#.....#.....##
#..#..#..#..#..#..##
#..#..#....##..#####
#.....#.....#..#####
#.....#..#..#..#..##
#..#..#.....#.....##
#..#..#....###...###
####################
####################
##..#..##...###...##
##..#..#.....#.....#
##..#..#..#..#..#..#
##..#..#..#..#..#..#
##.....#..#..#..#..#
###....#..#..#..#..#
#####..#.....#.....#
#####..##...###...##
####################
3 3 18 18
输出 #4
3
C++ 编辑器
输入
输出