Problem1101--着火的房间

1101: 着火的房间

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

Description

救救PIPI!!PIPI被关在一个着火的房间里了!
该房间中有 nxm 个位置, 用一个字符矩阵表示。
's' 代表PIPI的起点位置。
't' 代表出口位置。
'f' 代表房间的着火点。
'-' 代表房间还未着火的点。
房间里面有若干个着火点,每个着火点的移动速率是k , 意思是若一个位置在 x 时刻起火了,那么在 x+k 时刻它周围8个方向都会起火。
PIPI每秒能够移动到上下左右四个方向中的一个未着火的位置。
请你编程计算可怜的PIPI能否成功逃离这个房间,如果PIPI能够成功逃离这个房间,输出PIPI逃出房间的最短时间,如果PIPI不能逃出这个房间,输出"Impossible"。

Input

输入包含多组测试用例。
对于每一组测试用例,输入第一行包含三个整数 n,m,k .分别代表房间位置的行数,列数,以及着火点的移动速率。(1<=n,m,k<=100)
接下来输入一个n*m的字符矩阵,代表房间在0时刻的状态。
以0 0 0 代表输入结束。

Output

对于每组样例,输出一行。如果PIPI能够成功逃离这个房间,输出PIPI逃出房间的最短时间,如果PIPI不能逃出这个房间,输出"Impossible"。

Sample Input

7 7 2
f------
-f---f-
----f--
-------
------f
---s---
t----f-
3 4 1
t--f
--s-
----
2 2 1
st
f-
2 2 2
st
f-
0 0 0

Sample Output

4
Impossible
Impossible
1

Source/Category