1376_走迷宫II

一个迷宫可用类似于如下图的一个二维数组来描述：

.#..#
.#..#
....#
#.#..
#....

图  一个迷宫

图中，'.'表示可行走的通路，'#'表示障碍物，不可行走，也不可穿越。走迷宫时，只有上下左右四个方向可以行走，不可以斜着走，相邻两个位置距离为1。

假设此迷宫的入口坐标为(0, 0)（左上角），出口坐标为(4, 4)（右下角），则此迷宫可以通过如下的坐标序列（也可称为路径），从入口走到出口：

(0, 0)  (1, 0)  (2, 0)  (2, 1)  (2, 2)  (2, 3)  (3, 3)  (3, 4)  (4, 4)

显然，此迷宫的路径不止一条。

你的任务就是要找到长度最小的路径，输出从入口到出口的最小距离。

第一行是两个整数 m, n ，表示迷宫的长度和宽度。0 < m, n ≤ 50

第二行是4个整数 a, b, c, d，其中(a, b)表示迷宫的入口坐标，(c, d)表示出口坐标。

最下来有m行，每行n个字符。表示迷宫，字符含义如题所述。

对每个迷宫输出一行结果，如果该迷宫有解，则输出入口到出口的最小距离，否则输出-1。

5 5
0 0 4 4
.#..#
.#..#
....#
#.#..
#....

8

样例所示迷宫的一条最短路径为

(0,0)  (1,0)  (2,0)  (2,1)  (2,2)  (2,3)  (3,3)  (3,4)  (4,4)

距离为8