J8 例题-3 老鼠与迷宫

题目描述

有一只电子老鼠被困在迷宫中。这是一个 $12*12$ 单元的正方形迷宫，黑色部分表示建筑物，白色部分是路。电子老鼠可以在路上向上、下、左、右行走，每一步走一个格子。现给定一个起点 $S$ 和一个终点 $T$ ，求出电子老鼠最少要几步从起点走到终点。

输入格式

第一行有四个由空格分隔的整数，分别表示起点的坐标 $S(x,y)$ 和终点的坐标 $T(x,y)$ 。 从第二行开始的 $12$ 行中，每行有 $12$ 个字符，描述迷宫的情况，其中 $'X'$ 表示建筑物，$'.'$ 表示路。

注意：地图从 $(1,1)$ 开始，保证电老鼠能从起点走到终点。

输出格式

一个整数，即电子老鼠走出迷宫至少需要的步数。

样例输入

2 9 11 8
XXXXXXXXXXXX
X......X.XXX
X.X.XX.....X
X.X.XX.XXX.X
X.X.....X..X
X.XXXXXXXXXX
X...X.X....X
X.XXX...XXXX
X.....X....X
XXX.XXXX.X.X
XXXXXXX..XXX
XXXXXXXXXXXX

样例输出

28

样例分析

如上所述。

数据范围

如上所述。