Start: Jul, 31, 2022 18:00:00
2022-7-30Python培训班第二次作业(数据结构和算法)
End: Sep, 07, 2022 06:00:00
Time elapsed:
Time remaining:

HZNUacm跑跑卡丁车俱乐部 3025

Time Limit:  1 s      Memory Limit:   256 MB
Submission:8     AC:6     Score:0

Description

跑跑卡丁车是一款休闲益智类游戏。在HZNUacm俱乐部中,有着一批如方老师、殷老师,余老师、吞老师等优秀的跑跑卡丁车车手,而在一场竞赛中可以通过所有的近道来到达终点是他们的必备能力之一。现在,乘坐着“dyz521牌赛车”的楞老师并不打算直接前往终点,而是去帮一帮由于掉线而卡在原地不动的x-x老师。给定一个$n \times m $的地图, 地图中标记有楞老师当前的位置、x-x老师卡住的位置、赛道以及障碍物(“dyz521牌赛车”无法驶过障碍物),乘坐着“dyz521牌赛车”的楞老师开始位于当前位置, 每一秒乘坐着“dyz521牌赛车”的楞老师可向选择的方向(上、下、左、右)移动一格, 乘坐着“dyz521牌赛车”的楞老师经过$t$秒到达原地不动的x-x老师所在的位置帮助他。俱乐部长小志非常关心卡住的x-x老师,他想知道$t$的最小值,请你帮帮他。

Input

第一行给出两个正整数$n$、$m$ $(2 \leqslant n, m \leqslant 30)$,表示地图大小;

下面$n$行,每行$m$个字符, ‘S’ 表示乘坐着“dyz521牌赛车”的楞老师的起始位置, ‘E’表示原地不动的x-x老师,‘.’表示赛道,‘#’表示障碍物。

Output

输出一个最小的正整数$t$,表示楞老师到达x-x老师所在的位置所需时间,题目保证楞老师一定能到达x-x老师的位置,成功解救x-x老师的!

Samples

input
4 4 S... .... ...E ....
output
5
input
4 4 S#E. .... .... ....
output
4
input
6 6 S#E... .###.. .#.... .#.... ...... ......
output
14

Hint

样例解释:

样例一:楞老师向右走3步,向下走2步,就可以到达x-x老师的位置了。共花费5秒。

样例二:向下1步,向右2步,向上1步 共4秒。