Problem C: 行走与跳跃

Problem C: 行走与跳跃

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

Description

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