Problem D: PIPI找年货

Problem D: PIPI找年货

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 105  Solved: 25
[Submit] [Status] [Web Board] [Creator:]

Description

过年了,PIPI想要把屯的年货给吃掉,但是可恶的POPO不想把年货交给PIPI,于是他把年货藏在了某个地方
现在PIPI要从自己所在的位置出发,去把年货找出来,PIPI现在有一个传送器,他每秒钟可以向上下左右无障碍的地方行走一格,或者选择耗费传送器一格电进行传送。
传送就是按照“日”字进行一次移动,即从(x,y)可以到达(x+a,y+b)且1<=|a|,|b|<=2,|a|+|b|=3,该次移动可以无视过程中的障碍,但是如果传送达到的位置是障碍,则无法传送。
请问PIPI最少花费多少时间到达出口,若无法到达,输出impossible。

Input

多组输入。
第一行输入地图的长为m,宽为n,PIPI探测器拥有的电量k(1<m,n<=100,0<=k<=100)。
接下来输入一个大小为m*n的字符矩阵。
其中.代表空地,#代表障碍,S代表PIPI目前位置,T代表年货所在位置。

Output

对于每组输入,输出PIPI找到年货的最短时间,若PIPI无法找到年货,输出impossible。

Sample Input

3 3 1
.S.
.#.
.T.
3 4 2
S##.
#T#.
.#..

Sample Output

2
impossible