题目描述

小布在玩某个 $\tt 2D$ 迷宫游戏，迷宫由 $n$ 行 $m$ 列的格子组成，每个格子都为两种地形之一：

• 障碍以 * 表示，障碍不可通行；
• 空地以 . 表示，空地可以直接通行。

小布操控的角色从左上角出发，迷宫的出口在右下角，每次只能往上下左右相邻的格子移动。

由于障碍的存在导致角色不一定能走到出口，但是游戏中提供了一个魔法，施法后可以把任意一个格子转换成另一种地形。然而角色的 $\tt MP$ 有限，为了节省出 $\tt MP$ 应对后续的战斗关卡，小布希望在迷宫中施法的次数尽可能少，请你帮忙求出最少需要几次施法才能走到出口。

输入格式

第一行两个整数 $n,m$ 表示迷宫大小；
接下来是一个 $n$ 行 $m$ 列的字符矩阵，描述迷宫的地形，仅包含两种地形对应的字符。

输出格式

单个整数表示最少的施法次数。

输入输出样例 #1

输入 #1

4 4
....
.***
.*..
.*..

输出 #1

1

输入输出样例 #2

输入 #2

5 5
.....
.****
.*..*
.*..*
.****

输出 #2

3

说明/提示

数据范围

对于 $100\%$ 的数据，$1\leq n, m\leq 1000$。