← 返回题目列表

AtCoder · abc176_d

D. 迷宫中的巫师

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

分数: 400 点

问题陈述

迷宫由网格组成 H \times W 方块 - H 垂直, W 水平。

广场 i从顶部开始的第行和 j从左起第 - 列 - (i,j) - 是一堵墙,如果 S_{ij} is # 和一条路如果 S_{ij} is ..

里面有一个魔术师 (C_h,C_w)。他可以做以下两种动作:

  • 移动A:走到与他当前所在的方格垂直或水平相邻的道路方格。
  • 移动B:使用魔法将自己扭曲到道路方块中 5\times 5 以他当前所在广场为中心的区域。

无论哪种情况,他都无法走出迷宫。

他至少需要使用多少次魔法才能达到 (D_h, D_w)?

约束

  • 1 \leq H,W \leq 10^3
  • 1 \leq C_h,D_h \leq H
  • 1 \leq C_w,D_w \leq W
  • S_{ij} is # or ..
  • S_{C_h C_w} 和 S_{D_h D_w} 是 ..
  • (C_h,C_w) \neq (D_h,D_w)

输入

输入由标准输入按以下格式给出:

H W
C_h C_w
D_h D_w
S_{11}\ldots S_{1W}
\vdots
S_{H1}\ldots S_{HW}

输出

打印魔术师需要使用魔法的最少次数。如果他无法到达 (D_h,D_w),打印 -1 。


示例输入 1

4 4
1 1
4 4
..#.
..#.
.#..
.#..

示例输出 1

1

例如,步行至 (2,2) 然后使用魔法前往 (4,4),只需使用一次魔法就足够了。

请注意,他不能斜向行走。


示例输入 2

4 4
1 4
4 1
.##.
####
####
.##.

示例输出 2

-1

他无法从那里移动。


示例输入 3

4 4
2 2
3 3
....
....
....
....

示例输出 3

0

不需要使用魔法。


示例输入 4

4 5
1 2
2 5
#.###
####.
#..##
#..##

示例输出 4

2