题目内容

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

思路：动态规划

给定一个棋盘和一个棋子，棋子初始位于(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(因为方向变了，如果方向不变，可以将棋子移动任意步)。
2. $dp[i][j][1]$：从左上方$dp[i-1][j-1][0、1、2]$转移到当前格，与上面类似，有$dp[i][j][1] = min(dp[i-1][j-1][0]+1, dp[i-1][j-1][1], dp[i-1][j-1][2]+1)$。