编程题：迷宫问题之最短时间

小明某天不小心进入了一个迷宫（如上图所示），请帮他计算走出迷宫的最少的时间。规定每走一格需要1个单位时间。如果不能走到出口，则输出impossible。每次能走的仅有上、下、左、右4个方向。

### 输入格式:
测试数据有多组，处理到文件尾。每组测试数据首先输入2个整数n，m(0<n，m≤100)，代表迷宫的高和宽，然后n行，每行m个字符，其中各字符的含义如下：
'S'代表小明现在所在的位置；'T'代表迷宫的出口；'#'代表墙，不能走；'.'代表路，可以走；
'd'代表该位置有怪物，需额外使用d（1≤d≤9）个单位时间消灭怪物后方可进入该位置。

### 输出格式:
对于每组测试，输出走出迷宫的最少时间，若不能走出则输出impossible。

### 输入样例:
in
4 4
S8..
.1.#
#.#.
...T
4 4
S...
#..#
..#.
2.#T
9 13
#############
#S..2.......#
#####.#.#.#.#
#...........#
#.#.#.#.#.#.#
#.#.......#.#
#.#.#5#.#.#.#
#...........#
#####T#######


### 输出样例:
out
7
impossible
17


### 来源：
[1] 黄龙军,等. 数据结构与算法, 上海:上海交通大学出版社, 2022.7. ISBN: 9787313269881
[2] 黄龙军, 等. 数据结构与算法（Python版）, 上海: 上海交通大学出版社, 2023. （In Press）





answer：若无答案欢迎评论