题目描述

Reuben 正在玩 TNT RUN。游戏地图是一个  n*m  的网格，Reuben 的目标是找到从起点S到目标点 F 的最少步数。

在地图上，每个格子都是 TNT 方块，“神奇压力板”或虚空：


TNT 方块：当 Reuben 踩上 TNT 方块时，TNT 方块不会立即消失，但当它离开该方块后，TNT 方块会消失并变成虚空，无法再次踏上。因此，Reuben需要小心选择路径，确保不掉入虚空。


神奇压力板（用 # 表示）：当 Reuben 踩到神奇压力板时，会自动朝当前方向跳跃 4 格，无视路径上的 TNT 方块和虚空，这可以帮助 Reuben 安全地穿越危险区域，但Reuben不可超过地图外，地图外有空气墙。


Reuben 只能上下左右移动。


Reuben 从起点 S 出发，需要找到通往目标点 F 的最短路径。

输入格式

第一行包含两个整数  n  和  m （2 ≤  n, m  ≤ 15），表示地图的大小。

接下来  n  行，每行包含  m  个字符，描述游戏地图的布局：


S 表示 Reuben 的起点。


F 表示目标点。


* 表示 TNT 方块。


# 表示神奇压力板


.  表示虚空


确保有S和F点

输出格式

Reuben 能到达目标点 F，则输出最少步数，否则输出-1。

5 5
S****
*****
*****
****.
*#*.F

5

提示