逃出魔窟

逃出魔窟

背景

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%
上传者

相关

在下列比赛中:

泉州师院ACM_训练赛