题目描述

密室中有一张 $R\times C$ 的迷宫地图，. 表示可以通行，# 表示墙壁。霸王龙每一步只能向上、下、左、右移动到相邻的通路格。

已知起点和出口的位置，并保证一定可以到达。请计算从起点走到出口最少需要多少步。

输入格式

第一行包含两个整数 $R,C$。

第二行输入起点坐标 $s_x,s_y$。

第三行输入出口坐标 $t_x,t_y$。

接下来 $R$ 行，每行输入一个长度为 $C$ 的字符串，描述迷宫。

坐标从 $1$ 开始。

输出格式

输出从起点到出口的最少步数。

5 7
2 2
4 6
#######
#.....#
#.###.#
#.....#
#######

6

数据范围与提示

• $2\le R,C\le 500$，迷宫外围均为墙壁，起点和出口均为通路，并且出口可达