原神地图逃脱：D++的冒险之旅 - 最短路径求解

原神地图逃脱：D++的冒险之旅 - 最短路径求解

D++在114514年终于打开了原神，但他遇到了一个大麻烦——长丙文。D++想要摆脱长丙文的追捕，就必须逃出这张图，图中的格子都有技能，技能列表如下所示：

1. '.': 表示空地，可以直接走过去。
2. '#': 表示墙，无法走过去。
3. '?': 表示传送门，可以直接到达终点。

输入格式

第一行六个整数：n ，m ，a1 ，a2 ，b1 ，b2 表示地图的行与列，起点与终点。

接下来有 n 行 m 列的字符图。表示地图。

输出格式

共一行，一个整数，表示从 a 点到 b 点所需要的最少步数，若无法到达终点，则输出 -1 。

样例 #1

样例输入 #1

2 2 1 1 2 2
..
..

样例输出 #1

2

样例 #2

样例输入 #2

3 3 1 1 3 3
...
?##
...

样例输出 #2

2

约束条件

n < 20, m < 20

高级数据内容

样例 #3

样例输入 #3

3 4 1 1 3 4
....
..#.
?..#

样例输出 #3

5

样例 #4

样例输入 #4

4 5 1 2 4 3
.....
.....
?....
....#

样例输出 #4

6

样例 #5

样例输入 #5

5 5 1 1 5 5
.....
.....
...#.
.....
?....

样例输出 #5

-1

样例 #6

样例输入 #6

3 3 2 1 3 3
.#.
.#?
...

样例输出 #6

4

样例 #7

样例输入 #7

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

样例输出 #7

-1

样例 #8

样例输入 #8

5 5 1 1 5 5
.....
.....
.....
...#.
?....

样例输出 #8

-1

样例 #9

样例输入 #9

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

样例输出 #9

4

样例 #10

样例输入 #10

3 3 1 1 3 3
.#.
..#
?#.

样例输出 #10

-1