在一片树林中,发生了几处火灾,A小队接到了一个紧急任务,要从S点出发到T点,去保护T点的重要物资。
树林可以简化为n行m列的地图,该地图中字符'.'表示初始状态下该点没有着火,字符'F'表示初始状态下该点着火了,字符'S'表示出发点,字符'T'表示终点;当然起点和终点在初始状态下不会着火。
A小队每秒钟可以向上下左右四方向移动1步,着火的点每秒会蔓延到相邻的8个方向的位置,在任何时刻,A小队都无法移动到已经着火的位置上。
请问:A小队从S点出发,最短需要多久能到达T点,如果无论如何都无法到达T点,请输出-1。
第一行包含两个整数 n,m(0 < n, m <= 100)。
接下来 n 行给出一个字符矩阵,矩阵中字符的含义如题所述。
请输出从出发点到终点的最短时间是多少秒,如果无法到达终点,请输出-1。
8 10 .......... .F........ .......... .......... .......... ....S..... .........T ..........
6
6 10 .......... .......... .S........ .......... .........T ...FF.....
-1