← 返回题目

题库练习火灾救援

← 上一题下一题 →

A71379 | $火灾救援$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

在一片树林中，发生了几处火灾，A小队接到了一个紧急任务，要从 S 点出发到 T 点，去保护 T 点的重要物资。 树林可以简化为 n 行 m 列的地图，该地图中字符 . 表示初始状态下该点没有着火，字符 F 表示初始状态下该点着火了，字符 S 表示出发点，字符 T 表示终点；当然起点和终点在初始状态下不会着火。 A小队每秒钟可以向上下左右四方向移动 1 步，着火的点每秒会蔓延到相邻的 8 个方向的位置，在任何时刻，A小队都无法移动到已经着火的位置上。 请问：A小队从 S 点出发，最短需要多久能到达 T 点，如果无论如何都无法到达 T 点，请输出 -1 。

输入格式

第一行包含两个整数 n,m（0 \lt n, m \le 100）。 接下来 n 行给出一个字符矩阵，矩阵中字符的含义如题所述。

输出格式

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

输入输出样例

输入 #1

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

输出 #1

输入 #2

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

输出 #2

-1

C++ 编辑器

输入

输出