题目内容

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

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

输入描述

第一行包含两个整数 m, n (1 ≤ m, n ≤ 50)，表示迷宫的行数和列数。

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

• 0：表示通道
• 1：表示墙壁
• 2：表示虫洞
• S：表示起点
• E：表示终点

输出描述

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

样例1

输入

5 5
S0000
11100
01010
01010
0000E

输出

8

说明

在这个例子中，最短的路径如下所示： S -> (0,1) -> (0,2) -> (0,3) -> (0,4) -> (1,4) -> (2,4) -> (3,4) -> E 共8步。

样例2

输入

3 3
S00
111
E00

输出

-1

说明

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

样例3

输入

3 3
S02
111
E02

输出

4

说明

在这个例子中，最短的路径如下所示： S -> (0,1) -> (0,2) -> (2,1) -> E 共 4 步。 (0,2) 进入虫洞后，可直接从 (2,1) 出来，不消耗步数。