A4656. 冰雪世界

>时间限制：3S
空间限制：1024MB

我们的如烟大帝在一次时空旅行中来到了一个满是冰雪覆盖的世界，我们可以将其形象化地把这个世界视为由 $n \times m$ 个方格组成 $n$ 行 $m$ 列的棋盘，第 $i$ 行 $j$ 列(我们用 $a_{i,j}$ 表示)会存储一个字符#或*分别表示这个位置是障碍物或者可通过路径。现在如烟大帝在 $a_{1,1}$ 的位置，她需要前往 $a_{n,m}$ 才能逃出这个世界。每一次她可以选择上，下，左，右任意方向前进，并且每次前进时有两种前进方式：

* 消耗 $1$ 体力向前迈出一步到达相邻格子并使用秘术将自己停在此处
* 消耗 $1$ 体力向前迈出一步因为地面太滑直到碰到障碍物时才会停止

请你求出如烟大帝最少需要消耗多少体力到达终点，如果无论如何都无法到达输出-1。

注意我们默认地图以外的区域全部都是障碍物，并且题目保证起点和终点不是障碍物。

第一行输入两个正整数 n，m 表示棋盘行列 $(1 \le n,m \le 3000)$ 。

接下来 n 行每一行给出 m 个字符描述世界地形 $(a_{i,j} \in \{ ' \# ', ' *' \} )$ 。

输出一个整数为最终答案。