蝈蝈的迷宫

TimeLimit:2000MS  MemoryLimit:64MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

开门见山地说,一张n*m的地图,地图只包括以下元素:

① . 表示空地

② # 表示障碍物

③ S  表示起点

④ E  表示终点

⑤ K  表示钥匙

每次只能向上下左右移动,且每移动一格需要一单位时间,现在从起点开始,拿到一把钥匙,并到达终点,回答需要的最短单位时间

Input

单组数据

第一行两个整数n,m,表示地图的规格(2 ≤ n,m ≤ 1000)

接下来 n 行,每行一个字符串 m 个字符,表示地图


保证地图只有一个起点和一个终点

保证地图至少有一个钥匙

提示:如果没有钥匙,不能经过E终点的格子

Output

输出需要的最少单位时间,如果不能完成,则输出-1

SampleInput
5 5
S....
.....
..E..
.....
....K

5 5
S#..E
.#.#.
.#.#.
.#.#.
...#K
SampleOutput
12

-1

tip:-1是因为没有钥匙,不能经过E点,然而不经过E点,没法到K点,所以无法完成,输出-1
Submit
题目统计信息详细
总AC数17
通过人数15
尝试人数19
总提交量50
AC率30.00%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: