题目描述

有一个迷宫，每次只能往上下左右四个方向中的一个方向走一格，请算出从起点到终点的最短路径的长度。

迷宫用一个 $n$ 行 $m$ 列的字符矩阵表示，矩阵中存在 4 种字符：

• S 表示起点；
• E 表示终点；
• . 表示可以在上面移动的点；
• X 表示障碍物。

输入格式

第一行两个整数 $n,m$，表示迷宫的大小。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串。

数据保证起点和终点都只有一个。

输出格式

输出一个整数，表示最短路径的长度，如果不存在从起点到终点的路径输出 -1。

3 3
SXE
.X.
...

6

数据规模

对于所有数据，保证 $2≤n,m≤1000$。