#171. 「7-3」C 、 迷宫问题 暂未评定

时间限制:1000 ms 内存限制:128 MiB 输入文件:C.in 输出文件:C.out
题目类型:传统 评测方式:文本比较
上传者: root

注意

本题采用文件输入输出。

输入文件为 C.in, 输出文件为C.out

题目描述

一个网络迷宫有 m 行 n 列的单元格组成,每个单元格要么是空地(用 1 表示),要么是障碍物(用 0 表示)。在迷宫中行走时,每一步只能上下左右移动到相邻的格子中,且任何时候都不能在障碍格中,也不能走道迷宫之外。起点和终点保证是空地。
请你编程找到一条从起点到终点移动步数最少的路线。

输入格式

从文件 C.in 中读入数据。

第 1 行包含两个整数 m 和 n,表示迷宫是 m 行 n 列。

接下来的 m 行每行包含长度为 n 的 01 串,其中第 i+1 行的第 j 个字符是’0’,表示迷宫的第 i 行,

第 j 列是障碍物,是’1’表示迷宫的第 i 行第 j 列是空地。

最后一行包含四个整数:sx,sy,ex,ey,(sx,sy)表示起点行号和列号,(ex,ey)表示终点的行号 和列号。

注意:迷宫的行号和列号编号都是从 1 开始的。

输出格式

输出到文件 C.out 中。

第一行一个整数,表示最少的移动步数,若无解,则输出”None.”。

样例

样例输入

C.in

5 6
111111
100011
011111
110101
110111
2 5 5 1

样例输出

C.out

7

数据范围与提示

1<m,n<=25