迷宫问题(Maze)

题目描述

迷宫由 n 行 m 列的单元格组成，单元格中有一些是障碍（用 1 表示），可以通行的格子用 0 表示。你可以从上、下、左、右四个方向在可通行的格子间移动。求从起点 (p0, q0) 到终点 (p1, q1) 的最短路径长度（即经过的步数）。输入数据保证有解。

坐标 (p, q) 表示第 p 行、第 q 列，行列均从 1 开始编号。

输入格式

第一行两个整数 n 和 m。

接下来 n 行，每行 m 个字符（0 或 1，之间无空格），描述迷宫。

最后一行四个整数 p0、q0、p1、q1，分别表示起点和终点的行、列坐标。

输出格式

一个整数，表示从起点到终点的最短步数。

样例输入

5 4
0010
0000
0010
0100
0001
1 1 4 3

样例输出

7

样例说明：从左上角 (1,1) 出发到 (4,3)，例如路线 (1,1)→(2,1)→(2,2)→(2,3)→(2,4)→(3,4)→(4,4)→(4,3) 共 7 步，不存在更短的路线。

数据范围

• n, m ≤ 50；
• 迷宫字符中 0 表示可通行、1 表示障碍；
• 起点、终点保证是可通行格，且数据保证存在通路。