C0762 空间折叠
空间折叠
题目描述
在古老的星尘遗迹中，地面被划分为 H 行 W 列的石板网格。每块石板要么是完好的（用. 表示），要么是破碎的（用# 表示），只有完好石板才能安全站立。你从入口 (Ch,Cw) 出发，要前往祭坛 (Dh,Dw)。入口和祭坛保证是完好石板，且位置不同。
你可以执行以下两种行动：
- 步行：向上、下、左、右移动到相邻的完好石板。该行动 不消耗能量。
- 空间折叠：以当前石板为中心，向 5x5 的方形区域(即行偏移 -2 到 +2，列偏移 -2到 +2)内的任意完好石板瞬间传送。该行动消耗1点能量，且不能超出遗迹边界。
请你计算从入口到祭坛所需的最少能量消耗。如果无法到达，输出 -1。
输入
第一行，两个整数 H W。
第二行，两个整数 Ch Cw。
第三行，两个整数 Dh Dw。
接下来 H 行，每行一个长度为 W 的字符串，第 i 行表示迷宫的第 i 行, 其中 . 表示道路，# 表示墙壁。
输出
输出一个整数，表示最少能量消耗次数。若无法到达，输出 -1。
数据范围
1≤H,W≤10^3
1≤Ch,Dh≤H
1≤Cw,Dw≤W
迷宫中为 # 或 .
起点(Ch,Cw)和终点(Dh,Dw)均为道路。
起点与终点不同。
输入样例1
4 4
1 1
4 4
..#.
..#.
.#..
.#..
输出样例1
1
输入样例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