时空限制

2S/512M

题目描述

apiadu 走进了一个 $n$ 行 $m$ 列的森林。起初 apiadu 位于第 $1$ 行第 $1$ 列，他的目标是走到第 $n$ 行第 $m$ 列。

森林的地图由字符矩阵表示，包含以下几种符号：

• . ：表示空地，可以通过。
• # ：表示大树，视为障碍物，无法直接通过。
• F ：表示青蛙，该位置视为可以通行的空地，且带有一只青蛙。

apiadu 可以进行以下几种动作：

1. 移动：花费 $1$ 秒向上下左右四个方向中的一个移动一格。前提是目标格子不能是大树，且不能走出森林边界。
2. 拾取：如果 apiadu 当前所在的位置有青蛙，且他手中没有青蛙，则可以花费 $1$ 秒将这只青蛙捡起。捡起后，该位置的青蛙消失。
3. 投掷：如果 apiadu 手中有青蛙，且向上下左右某个方向紧邻的格子是大树（#），他可以花费 $1$ 秒将青蛙向该方向投掷（投掷后 apiadu 的手里没有青蛙）。投掷后，该位置的大树被摧毁，变成空地 .。投掷青蛙后，apiadu 必须 紧接着花费 $1$ 秒移动到这个新产生的空地上。当 apiadu 离开这个新产生的空地后，该位置会立即重新长出大树（变回 #）。

请计算 apiadu 到达终点需要多少秒。题目保证 apiadu 一定能到达终点。

格式

输入格式

第一行包含两个整数 $n, m$，表示森林的大小。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示森林的地图。

输出格式

输出一行一个整数，表示到达终点的最小秒数。

样例

样例输入 #1

3 4
.F#.
.###
.#..

样例输出 #1

9

样例解释 #1

apiadu 可以按照以下顺序行动：

1. 向右移动到 $(1, 2)$（此处有青蛙），花费 $1$ 秒。
2. 拾取青蛙，花费 $1$ 秒。此时手中持有青蛙。
3. 向左移动回 $(1, 1)$，花费 $1$ 秒。
4. 向下移动到 $(2, 1)$，花费 $1$ 秒。
5. 向下移动到 $(3, 1)$，花费 $1$ 秒。
6. 向右投掷青蛙，摧毁 $(3, 2)$ 的大树，花费 $1$ 秒。
7. 紧接着向右移动到 $(3, 2)$，花费 $1$ 秒。此时 $(3, 2)$ 为空地。
8. 向右移动到 $(3, 3)$，花费 $1$ 秒。apiadu 离开 $(3, 2)$，该位置立即变回大树。
9. 向右移动到 $(3, 4)$，到达终点，花费 $1$ 秒。

总计 $1+1+1+1+1+1+1+1+1 = 9$ 秒。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，满足 $1 \le n, m \le 1000$。保证地图第 $1$ 行第 $1$ 列和第 $n$ 行第 $m$ 列是 .。