题目描述

给定 $n\times m$ 个方格构成的图，每个格子都有一种地形：

• 有一些格子是障碍，以符号 * 表示，障碍不可通行，移除后可以通行。
• 有一些格子是空地，以符号 . 表示，空地可以直接通行。

请计算从左上角的方格出发，行走到右下角，最少需要移除多少障碍。行走时，只能移动到水平或垂直方向相邻的方格。

输入格式

• 第一行：单个整数 $n$ 与 $m$
• 第二行到第 $n+1$ 行：第 $i+1$ 行每行有 $m$ 个整数表示第 $i$ 行的地形

输出格式

• 单个整数表示答案

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

1

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

3

数据范围

• $50\%$ 的数据，$n, m\leq10$
• $100\%$ 的数据，$2\leq n, m\leq1000$
• 保证左上角方格的地形为空地。