Problem A: 迷宫最短路径

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:14 Solved:11

Description

给定一个 的迷宫,迷宫由以下元素组成:
. 表示可通行的路
# 表示墙(不可通行)
S 表示起点(只有一个)
E 表示终点(只有一个)
求从起点 S 到终点 E最短路径长度(即最少需要走多少步)。如果无法到达终点,输出 -1
移动规则:每次可以向上下左右四个方向移动一步,不能斜着走,不能走出迷宫边界。


Input

第一行包含两个整数 ),表示迷宫的行数和列数。
接下来 行,每行 个字符,表示迷宫的布局。
保证迷宫中恰好有一个 S 和一个 E

Output

输出一个整数,表示从 SE 的最短路径长度。如果无法到达,输出 -1

Sample Input Copy

4 4
S..#
#.#.
....
#..E

Sample Output Copy

6