1224. 简单迷宫问题

单点时限: 2.0 sec

内存限制: 256 MB

一天,sunny 不小心进入了一个迷宫,不仅很难寻找出路,而且有的地方还有怪物,但是 sunny 有足够的能力杀死怪物,但是需要一定的时间,但是 sunny 想早一点走出迷宫,所以请你帮助他计算出最少的时间走出迷宫,输出这个最少时间。

我们规定每走一格需要时间单位 1, 杀死怪物也需要时间 1, 如果不能走到出口,则输出 impossible. 每次走只能是上下左右 4 个方向。

输入格式

每次首先 个数 ,代表迷宫的高和宽,然后 行,每行 个字符。

  • S 代码你现在所在的位置。
  • T 代表迷宫的出口。
  • # 代表墙,你是不能走的。
  • X 代表怪物。
  • . 代表路,可以走。

处理到文件结束。

输出格式

输出最少的时间走出迷宫。不能走出输出 impossible

样例

Input
4 4
S.X.
#..#
..#.
X..T
4 4
S.X.
#..#
..#.
X.#T
Output
6
impossible

151 人解决,296 人已尝试。

226 份提交通过,共有 1513 份提交。

4.4 EMB 奖励。

创建: 12 年,2 月前.

修改: 1 年,10 月前.

最后提交: 1 周,6 天前.

来源: LSP

题目标签