英语题目翻译——OJ_ 8436:Saving Tang Monk

题目：8436:Saving Tang Monk（OpenJudge - 8436:Saving Tang Monk）

翻译：

《西游记》(又称《美猴王》)是中国文学四大名著之一。它是吴承恩在明朝时写的。在这部小说中，孙悟空、猪八戒和沙悟净陪同唐僧去印度取经。

途中，唐僧常被妖怪捉住。大多数妖怪为了长生不老想要吃唐僧，但有些女妖怪只是因为唐僧英俊而想嫁给他。所以，孙悟空的主要工作是保护唐僧，帮助唐僧打败妖怪。

有一次，唐僧被白骨精抓走了。白骨精住在宫殿里，她把唐僧铐在房间里。孙悟空设法进入了宫殿。但是为了救唐僧，孙悟空需要一些钥匙并且杀死挡道的蛇。

这座宫殿可以被描述成一个矩阵。每个格子代表一个房间。在矩阵中，“K”代表孙悟空原来的位置，“T”代表唐僧的位置，“S”代表有蛇的房间。请注意，只有一个“K”和一个“T”，宫殿里最多有五条蛇。“#”是指一个孙悟空进不去的致命房间。

房间里可能有一些不同种类的钥匙，但一个房间里最多只有一把。最多有9种钥匙。有钥匙的房间用数字(从1到9)表示。例如，“1”表示房间里有第一类钥匙，“2”表示房间里有第二类钥匙，“3”表示房间里有第三类钥匙……等。为了救唐僧，孙悟空必须得到各种各样的钥匙(也就是说，每种钥匙至少有一个)。

孙悟空每走一步，就可以从北、西、南、东四个方向走到相邻的房间(死亡的房间除外)，每走一步需要1分钟。如果他进入一个有活蛇居住的房间，他必须杀死这条蛇。杀死一条蛇也需要一分钟。如果孙悟空进入一间有N种钥匙的房间，当且仅当他已经有了1类、2类...和n-1类钥匙时，他才会得到那把钥匙。换句话说，孙悟空在得到N+1 (N>=1)之前，必须得到N类型的钥匙。如果孙悟空拿到了所有的钥匙，进入了唐僧被铐住的房间，营救任务就完成了。如果孙悟空没有拿到足够的钥匙，他仍然可以通过唐僧的房间。由于孙悟空是一只没有耐心的猴子，他想尽快救出唐僧。请算出孙悟空救出唐僧的最短时间。

输入
有好几组数据。
对于每种情况，第一行包含两个整数N和M(0 < N <= 100, 0<=M<=9)，这意味着宫殿是一个N×N矩阵，孙悟空需要M种钥匙(第1种，第2种，…第M种)。
然后是N×N矩阵。
输入以N = 0和M = 0结束。
输出
对于每个测试用例，打印孙悟空拯救唐僧所需的最小时间(以分钟为单位)。如果孙悟空不可能完成任务，就打印“impossible”(不要引号)。

样例输入

3 1
K.S
##1
1#T
3 1
K#T
.S#
1#.
3 2
K#T
.S.
21.
0 0

样例输出

5
impossible
8