思路：动态规划

给定一个棋盘和一个棋子，棋子初始位于(1,1)，棋盘由"."、"*"组成，"."可以行走而"*"不行。每次可以将棋子向右、向下、向右下移动若干格，求移动到最右下所需要的步数。

可以发现，走到当前格子所需要的步数和上方格子，左上方格子以及左方格子有关，可以考虑动态规划解决。

定义：$dp[i][j][0、1、2]$分别表示从上方、从左上方、从左方走到(i,j)所需要的最小的步数

1. $dp[i][j][0]$：从上方$dp[i-1][j][0、1、2]$转移到当前格，根据状态方程的定义，有$dp[i][j][0] = min(dp[i-1][j][0], dp[i-1][j][1]+1, dp[i-1][j][2]+1)$。即，如果上方格子也是从上方转移来的，那么不用+1，否则另两个方向转移来的需要+1(因为方向变了，如果方向不变，可以将棋子移动任意步)。

题目内容

小红有一个$n$行$m$列的棋盘，并且有一个棋子初始位于(1,1)。

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

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

输入描述

第一行，两个正整数$n$和$m$。

接下来的$n$行，每行$m$个字符，用来表示棋盘

$1 \leq n,m \leq 2000$

输出描述

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

样例

输入

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

输出

2