2446 - 火灾救援

题目描述

在一片树林中,发生了几处火灾,A小队接到了一个紧急任务,要从 S 点出发到 T 点,去保护 T 点的重要物资。

树林可以简化为 nm 列的地图,该地图中字符 '.' 表示初始状态下该点没有着火,字符 'F' 表示初始状态下该点着火了,字符 'S' 表示出发点,字符 'T' 表示终点;当然起点和终点在初始状态下不会着火。

A小队每秒钟可以向上下左右四方向移动 1 步,着火的点每秒会蔓延到相邻的 8 个方向的位置,在任何时刻,A小队都无法移动到已经着火的位置上。

请问:A小队从 S 点出发,最短需要多久能到达 T 点,如果无论如何都无法到达 T 点,请输出 -1

输入

第一行包含两个整数 n,m0 \lt n, m \le 100)。

接下来 n 行给出一个字符矩阵,矩阵中字符的含义如题所述。

输出

请输出从出发点到终点的最短时间是多少秒,如果无法到达终点,请输出 -1

样例

输入

8 10
..........
.F........
..........
..........
..........
....S.....
.........T
..........

输出

6

输入

6 10
..........
..........
.S........
..........
.........T
...FF.....

输出

-1
标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题