逃出生天
小明一觉醒来发现家中着火,为了保障生命安全,必须第一时刻逃出房间。由于火势太大,小明无法穿越或者靠近火堆。如果长时间呆在火场中,小明将受到烟雾威胁,吸入过多的一氧化碳昏迷,所以请你计算小明最快要多少时间逃出火灾场。如果小明无法逃出,请输出IMPOSSIBLE。
靠近的定义是两个方块相邻,即有公共边。
小明的房间大小为n * m, S点标记为小明的所在位置,T点为出口。
输入说明
首先输入n, m。
接下来n行,每行输入一串长为m的字符。
其中‘# 表示为火, '.'表示为安全的地方
‘S’表示为小明所在的位置, ‘T‘ 表示逃生出口
对于50%的数据 n, m <= 50;
对于100%的数据,n, m <= 500;
数据保证起点与终点附近无‘#’
输出说明
如果小明能够逃出生天,请输出小明所需要花费的时间,如果不能,请输出“IMPOSSIBLE”;
样例
输入:
5 5
S...T
..#..
.....
.....
.....
输出:
10
解释:由于小明无法穿越或者靠近火堆,所以小明不能直接第一行到达出口,必须到达第四行才能安全穿越。