题目描述
一天,sunny 不小心进入了一个迷宫,不仅很难寻找出路,而且有的地方还有怪物,但是 sunny 有足够的能力杀死怪物,但是需要一定的时间,但是 sunny 想早一点走出迷宫,所以请你帮助他计算出最少的时间走出迷宫,输出这个最少时间。
我们规定每走一格需要时间单位 1, 杀死怪物也需要时间 1, 如果不能走到出口,则输出impossible. 每次走只能是上下左右 4 个方向。
输入
每次首先 2 个数 n,m (0<n,m≤200),代表迷宫的高和宽,然后 n 行,每行 m 个字符。
S代码你现在所在的位置。
T代表迷宫的出口。
#代表墙,你是不能走的。
X代表怪物。
.代表路,可以走。
处理到文件结束。
输出
输出最少的时间走出迷宫。不能走出输出impossible。
样例输入 Copy
4 4
S.X.
#..#
..#.
X..T
4 4
S.X.
#..#
..#.
X.#T
样例输出 Copy
6
impossible