题目描述
小李带领一群同学玩密室逃脱游戏，密室为一个 n×m 方格的迷宫房间，迷宫有若 干墙壁、陷阱和出口，小李每次可以向上、下、左、右其中一个方向移动一格，正常方 格用时 1 秒，陷阱方格用时 3 秒，但不能移动到墙壁方格。作为队长，小李需要找出最 快逃离密室的路径并涂上特殊的荧光粉，以引导其他同学逃离。请你给小李编程求出离 开迷宫最少需要多少秒。
输入
第一行两个正整数 n，m(n,m≤1000)。接下来 n 行，每行 m 个字符,字符含义如下: '.' --该位置可以正常行走方格
'@'--该位置为迷宫中的陷阱方格
'#' --该位置为迷宫中的墙壁方格
'S' --该位置为小李出发的位置方格
'E' --该位置为迷宫的出口方格
输出
一行，一个整数表示逃离密室最短时间。如果小李无法到达出口，输出“The End!!!”。
样例输入输出
输入#2
复制
4 5
S..@@
@.#@@
@..#E
#....
提示
其中 30%的数据，n，m<=100，无陷阱;
另有 30%的数据，n，m<=100，有陷阱;
另有 20%的数据，n，m<=1000，无陷阱;
另有 20%的数据，n，m<=1000，有陷阱;