原神地图寻宝：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

高级数据样例：

样例输入 #1

2 2 1 1 2 2 '..' '..'

样例输出 #1

2

样例输入 #2

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

样例输出 #2

2

样例输入 #3

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

样例输出 #3

4

样例输入 #4

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

样例输出 #4

-1

样例输入 #5

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

样例输出 #5

-1

样例输入 #6

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

样例输出 #6

4

样例输入 #7

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

样例输出 #7

3

样例输入 #8

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

样例输出 #8

-1

样例输入 #9

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

样例输出 #9

4

样例输入 #10

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

样例输出 #10

4