#P1463. 2023.08.19-JD-第三题-塔子哥走棋

2023.08.19-JD-第三题-塔子哥走棋

题目内容

塔子哥有一个nnmm列的棋盘,并且有一个棋子初始位于(1,1)。

棋盘由字符"."、"*"组成,"."代表该位置可行走,"*"代表该位置不能行走。

塔子哥每次可以让棋子往右,往下或者往右下移动若干个位置,他想知道,移动到右下角(n,m)一共需要多少步?

输入描述

第一行,两个正整数nnmm

接下来的nn行,每行mm个字符,用来表示棋盘

1n,m20001 \leq n,m \leq 2000

输出描述

一个整数,表示所需要的最少步数

样例

输入

4 3
...
.*.
...
**.

输出

2