UOJ Logo

NOI.AC

1S 512MB

#1735. 逃出生天

统计

逃出生天

小明一觉醒来发现家中着火,为了保障生命安全,必须第一时刻逃出房间。由于火势太大,小明无法穿越或者靠近火堆。如果长时间呆在火场中,小明将受到烟雾威胁,吸入过多的一氧化碳昏迷,所以请你计算小明最快要多少时间逃出火灾场。如果小明无法逃出,请输出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

解释:由于小明无法穿越或者靠近火堆,所以小明不能直接第一行到达出口,必须到达第四行才能安全穿越。