逃出魔窟
背景
17陷入了一个魔窟中,他必须要在最短的时间内从起点'S'
走到终点'E'
。17可以向与他相邻的四个方格中的其中一个前进一步,每走一步都需要花费1时间。特别的是,在这个魔窟中的某个位置有一个陷阱'T'
,只有带上保护膜才可以顺利通过,而魔窟中会有一点'P'
代表保护膜,只要经过那里就会自动带上。另外,'.'
代表魔窟中安全地带,可任意经过,'#'
代表墙壁,无法穿过。问17逃出魔窟最少需要多长时间。
输入
第一行有两个正整数m和n,代表魔窟的大小。(2<=m,n<=20)
接下来的m行代表魔窟,每行有n个字符,这些字符只包含'S'
, 'E'
, '#'
, 'T '
, 'P'
, '.'
。
其中起点'S'
,终点'E'
,陷阱'T'
,保护膜'P'
有且只有一个。
输出
在一行中输出一个整数代表答案,如果无法从起点走到终点,则输出-1。
样例输入
2 10
E.#.S..#.P
..T..#....
样例输出
20
信息
- 难度
- 8
- 分类
- (无)
- 标签
- 递交数
- 46
- 已通过
- 9
- 通过率
- 20%
- 上传者
相关
在下列比赛中: