山火撤离

题目背景

护林员小 R 在山里的观测站值班时，远处突然起了山火。观测站建在一片由岩石与空地交错组成的山坡上，火势顺着空地蔓延。小 R 必须尽快走到山坡的边缘才能脱险。

题目描述

山坡可以看成一个 $n$ 行 $m$ 列的网格，每个格子是下列四种之一：

• .：可以通行的空地；
• #：无法穿越的岩石；
• F：火源（可能有多处，也可能一处都没有）；
• S：小 R 出发的位置（恰好一处）。

时间从第 $0$ 分钟开始。每一分钟按下面的顺序发生两件事：

1. 小 R 先移动：他从当前格子走向上、下、左、右四个方向中相邻的一个格子，也可以留在原地不动。他不能走进岩石，也不能走进已经燃烧的格子；
2. 火再蔓延：所有已经燃烧的格子会向四个方向相邻的空地蔓延一格（岩石不会被点燃，火也烧不过岩石）。

若某个格子在第 $t$ 分钟的火蔓延中被点燃，那么人在第 $t$ 分钟结束时以及之后都不能位于这个格子上；人只要在第 $T$ 分钟结束时位于一个尚未燃烧的边界格子，就说明他在第 $T$ 分钟撤离成功。

边界格子指的是第 $1$ 行、第 $n$ 行、第 $1$ 列或第 $m$ 列上的任意格子。如果小 R 一开始就站在边界格子上，那么他在第 $0$ 分钟就已经成功撤离，耗时 $0$ 分钟。

请你求出小 R 最早能在第几分钟撤离。如果无论如何都无法撤离，输出 $-1$。

输入格式

从标准输入读入数据。

第一行两个整数 $n, m$。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，字符含义如题面所述。保证恰好有一个 S。

输出格式

输出到标准输出。

一行一个整数，表示最早的撤离分钟数；若无法撤离，输出 -1。

样例 1 输入

3 5
.....
.S..F
.....

样例 1 输出

1

样例 1 解释

小 R 向上走一格到达第 $1$ 行第 $2$ 列，这是第 $1$ 行上的边界格子，此时火才刚刚从第 $2$ 行第 $5$ 列蔓延，远没有烧到那里，所以耗时 $1$ 分钟。

样例 2 输入

3 3
###
#S#
###

样例 2 输出

-1

样例 2 解释

四周全是岩石，一步也走不出去，无法抵达边界。

样例 3 输入

3 3
...
.S.
..F

样例 3 输出

1

样例 3 解释

没有岩石，火只有一处（起点在右下角）。小 R 只要向上或向左走一格就到达边界，只需 $1$ 分钟。

特殊性质

• 特殊性质 A：地图上没有火源（一个 F 都没有）。此时只要判断小 R 能否走到边界，问题退化成一次普通的广度优先搜索。
• 特殊性质 B：地图上只有一个火源，并且没有任何岩石（除了 S、F 以外全是 .）。此时每个格子的着火时刻可以直接算出来，最容易逐分钟模拟。

数据范围与子任务

提交说明

本题使用标准输入输出。程序应从标准输入读入数据，并将答案输出到标准输出。