2446 - 【基础】火灾救援

题目描述

在一片树林中,发生了几处火灾,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
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
统计
上一题 下一题