思路：动态规划

给定一个棋盘和一个棋子，棋子初始位于(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)$。
3. $dp[i][j][2]$：从左方$dp[i][j-1][0、1、2]$转移到当前格，与上面类似，有$dp[i][j][2] = min(dp[i][j-1][0]+1, dp[i][j-1][1]+1, dp[i][j-1][2])$。
4. 如果当前格子为"*"，那么$dp[i][j][0、1、2]=∞$

时间复杂度为$O(NM)$。

代码

C++

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int T;
char s[2005][2005];
int dp[2005][2005][3];
int n, m;

int main() {
    scanf("%d %d", &n, &m); // 输入 n 和 m
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s[i] + 1); // 输入地图的每一行
    }
    memset(dp, 0x7f, sizeof(dp)); // 初始化 dp 数组为最大值
    dp[1][1][0] = 1;
    dp[1][1][1] = 1;
    dp[1][1][2] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i][j] == '*') {
                dp[i][j][0] = 1e9; // 如果当前位置是障碍物，将对应 dp 值设置为一个大数
                dp[i][j][1] = 1e9;
                dp[i][j][2] = 1e9;
                continue;
            }
            if (i == 1 && j == 1) continue; // 起始位置特殊处理
            dp[i][j][0] = min(dp[i - 1][j][0], min(dp[i - 1][j][1] + 1, dp[i - 1][j][2] + 1));
            dp[i][j][1] = min(dp[i - 1][j - 1][0] + 1, min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2] + 1));
            dp[i][j][2] = min(dp[i][j - 1][0] + 1, min(dp[i][j - 1][1] + 1, dp[i][j - 1][2]));
        }
    }
    int ans = 1e9; // 初始化答案为一个大数
    ans = min(ans, dp[n][m][0]);
    ans = min(ans, dp[n][m][1]);
    ans = min(ans, dp[n][m][2]);
    if (ans >= 1e9) {
        printf("-1"); // 输出结果
    } else {
        printf("%d", ans);
    }

    return 0;
}

python

n, m = map(int, input().split())  # 输入 n 和 m
s = [['']] * 2005  # 二维列表存储地图
for i in range(1, n + 1):
    s[i] = [''] + list(input())  # 输入地图的每一行

dp = [[[float('inf')] * 3 for _ in range(m + 1)] for _ in range(n + 1)]  # 初始化 dp 数组为最大值
dp[1][1][0] = 1
dp[1][1][1] = 1
dp[1][1][2] = 1
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s[i][j] == '*':
            dp[i][j][0] = float('inf')  # 如果当前位置是障碍物，将对应 dp 值设置为正无穷
            dp[i][j][1] = float('inf')
            dp[i][j][2] = float('inf')
            continue
        if i == 1 and j == 1:
            continue  # 起始位置特殊处理
        dp[i][j][0] = min(dp[i - 1][j][0], min(dp[i - 1][j][1] + 1, dp[i - 1][j][2] + 1))
        dp[i][j][1] = min(dp[i - 1][j - 1][0] + 1, min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2] + 1))
        dp[i][j][2] = min(dp[i][j - 1][0] + 1, min(dp[i][j - 1][1] + 1, dp[i][j - 1][2]))

ans = float('inf')  # 初始化答案为正无穷
ans = min(ans, dp[n][m][0])
ans = min(ans, dp[n][m][1])
ans = min(ans, dp[n][m][2])
if ans == float('inf'):
    print("-1")  # 输出结果
else:
    print(int(ans))

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 输入 n
        int m = scanner.nextInt(); // 输入 m
        
        char[][] s = new char[2005][2005]; // 二维数组存储地图
        for (int i = 1; i <= n; i++) {
            s[i] = (" " + scanner.next()).toCharArray(); // 输入地图的每一行
        }
        
        int[][][] dp = new int[2005][2005][3]; // 初始化 dp 数组
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = 1_000_000_000; // 初始化为一个大数
            }
        }
        dp[1][1][0] = dp[1][1][1] = dp[1][1][2] = 1;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i][j] == '*') {
                    dp[i][j][0] = dp[i][j][1] = dp[i][j][2] = 1_000_000_000; // 如果是障碍物，设为大数
                    continue;
                }
                if (i == 1 && j == 1) continue; // 起始位置特殊处理
                dp[i][j][0] = Math.min(dp[i - 1][j][0], Math.min(dp[i - 1][j][1] + 1, dp[i - 1][j][2] + 1));
                dp[i][j][1] = Math.min(dp[i - 1][j - 1][0] + 1, Math.min(dp[i - 1][j - 1][1], dp[i - 1][j - 1][2] + 1));
                dp[i][j][2] = Math.min(dp[i][j - 1][0] + 1, Math.min(dp[i][j - 1][1] + 1, dp[i][j - 1][2]));
            }
        }
        
        int ans = 1_000_000_000; // 初始化答案为一个大数
        ans = Math.min(ans, dp[n][m][0]);
        ans = Math.min(ans, dp[n][m][1]);
        ans = Math.min(ans, dp[n][m][2]);
        
        if (ans >= 1_000_000_000) {
            System.out.print("-1"); // 输出结果
        } else {
            System.out.print(ans);
        }
    }
}

题目内容

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

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

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

输入描述

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

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

$1 \leq n,m \leq 2000$

输出描述

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

样例

输入

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

输出

2