题目描述

给定一个迷官的地图，地图是一个二维矩阵，其中 $0$ 表示通道，$1$ 表示墙壁，$s$ 表示起点，$E$ 表示终点。你需要从起点 $S$ 出发，通过最路径到达终点 $E$ ，返回最短路径的步数，如果无法到达终点，则返回 $-1$，迷宫中会有虫洞，用数字 $2$ 表示，成对出现，你走入虫洞可以穿越到下一个虫洞出口，耗费 $0$ 步（也可以从下一个虫洞穿越到当前虫洞）。

你只能上下左右移动，并且不能走出迷官的边界，也不能穿越墙壁

输入描述

第一行输入两个整数 $m,n(1\le m,n\le 50)$ ，表示迷宫的行数和列数。

接下来的 $m$ 行，每行输入 $n$ 个字符，表示迷宫的地图。字符为：

$0$：表示通道

$1$：表示墙壁

$2$：表示虫洞

$S$：表示起点

$E$：表示终点

输出描述

如果能够到达终点，输出最短路径的步数。 如果无法到达终点，输出 $-1$ 。

样例1

输入

5 5
S0000
11110
01010
01010
0000E

输出

8

样例解释

在这个例子中，最短的路径如下所示：

$S\to (0,1)\to (0,2)\to (0,3)\to (0,4)\to (1,4)\to (2,4)\to (3,4)\to E$

共8步。

样例2

输入

3 3
S00
111
E00

输出

-1

样例解释

在这个例子中，起点 $5$ 和终点 $E$ 被墙壁阻隔，因此无法到达终点，输出 $-1$ 。

样例3

输入

3 3
S02
111
E02

输出

4

样例解释

在这个例子中，最短的路径如下所示：

$S \to (0,1)\to (0,2)\to (2,1)\to E$ 共 $4$ 步。

$(0,2)$ 进入虫洞后，可直接从 $(2,1)$ 出来，不消耗步数