网格最短步数

难度：T2

【知识点：搜索与状态】

前置知识：DFS、BFS、数组队列、已学剪枝。

题目描述

网格中.为空地，#为墙。每步只能上下左右移动一格，不能出界或经过墙。给定起点与终点，求最少移动步数。起终点可能相同，此时0步；无法到达输出-1。

输入格式

第一行n m，接着n行每行m个字符。最后一行sr sc tr tc依次是起点和终点行列。坐标从1开始，保证起终点为空地。

输出格式

一行最少步数或-1。

样例输入

2 3
...
...
1 1 2 3

样例输出

3

样例解释

向右两次、向下一次，共3步，不能少于横纵坐标差之和。

数据范围

1≤n,m≤30。