C1132 - 迷宫最短路径
题目描述
一个迷宫由r行c列格子组成，有的格子有障碍物，不能走；有的格子是空地，可以走。
现在给定一个迷宫数据，求从指定的出发坐标走到终点坐标最少需要的步数。
只能往水平方向或者竖直方向走，不能斜着走。
输入格式
第1行，两个正整数r和c，分别代表迷宫的长和宽
接下来r行，每行c个字符，代表整个迷宫
空地格子使用.表示，有障碍物的格子用#表示
接下来1行，是出发点坐标x1和y1，用空格分隔（起点坐标为(1,1)
接下来1行，是终点坐标x2和y2，用空格分隔（终点坐标为(r,c))
起点和终点坐标不会相同
输出格式
输出从出发坐标(x1, y1)到终点坐标(x2, y2)所需要的最少的步数（即至少要经过多少个空地格子）。计算步数要包括起点和终点
如果不能从(x1, y1)走到(x2, y2)则输出-1（包括起点坐标、终点坐标的迷宫为#的情形）
样例 #1 输入
5 5
..###
#....
#.#.#
#.#.#
#.#..
1 1
5 5
样例 #1 输出
9
样例 #2 输入
5 5
..###
#....
#.#.#
#.#.#
#.#..
1 1
1 3
样例 #2 输出
-1
数据范围与提示
100%的数据：$1 \le r, c\le 40$，
出发点坐标和终点坐标都在合理的范围内，即在[1,1]到[r,c]之间
测试点数目
共10个测试点，每个测试点10分
时间与内存限制
每个测试点时间：1000ms（1.0s），内存：256MiB
输入输出模式
本OJ支持两种输入输出模式
1. 标准输入输出模式：
直接从标准输入和标准输出读写数据，不需要使用freopen进行文件输入输出重定向
2. 文件输入输出模式（国内信奥赛输入输出模式）:
从文件中读写数据，需要使用freopen进行输入输出重定向
本题输入文件名为：C1132.in，输出文件名为：C1132.out