题解 | #小红的皇后#

题目链接

小红的皇后

题目描述

有一个 $n \cdot m$ 的棋盘，有一些格子是障碍物不能通过。小红控制一个皇后从左上角出发，每次移动她可以控制皇后进行以下三种方式中的一种：

向右移动若干个格子
向下移动若干个格子
向右下移动若干个格子（斜向移动）

移动的前提是路径上没有障碍物。小红想知道，皇后从左上角移动到右下角，最少要移动多少步？

输入:

第一行输入两个正整数 $n$ 和 $m$ ，代表行数和列数
接下来的 $n$ 行，每行输入一个长度为 $m$ 的字符串，用来表示棋盘
其中'.'代表可以通过的位置，'*'代表障碍物
保证左上角和右下角都不是障碍物

输出:

如果无法到达，请输出 $-1$
否则输出一个整数，代表最少的移动次数

解题思路

这是一个动态规划问题，可以通过以下步骤解决：

关键发现：
- 每次移动可以选择三个方向：向下、向右、右下
- 每次移动的方向会影响下一步的最小步数
- 可以用状态转移来解决最小步数问题
解题策略：
- 使用三维DP数组，第三维表示当前移动方向
- 状态转移时考虑从不同方向到达当前位置
- 如果是障碍物则跳过该位置
具体步骤：
- dp[i][j][k] 表示到达位置(i,j)且最后一步方向为k的最小步数
- k=0表示向下，k=1表示向右，k=2表示右下
- 初始化起点的三个方向都为1
- 状态转移时考虑从三个方向转移而来，如果改变方向则步数+1

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> ch(n);
    for(int i = 0; i < n; i++) {
        cin >> ch[i];
    }
    
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(3, n*m)));
    
    dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = 1;
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(ch[i][j] == '*') continue;
            for(int k = 0; k < 3; k++) {
                if(i-1 >= 0) {
                    dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][k] + (k != 0));
                }
                if(j-1 >= 0) {
                    dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][k] + (k != 1));
                }
                if(i-1 >= 0 && j-1 >= 0) {
                    dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-1][k] + (k != 2));
                }
            }
        }
    }
    
    int ans = min({dp[n-1][m-1][0], dp[n-1][m-1][1], dp[n-1][m-1][2]});
    if(ans >= n*m) cout << -1 << endl;
    else cout << ans << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] ch = new char[n][m];
        for(int i = 0; i < n; i++) {
            ch[i] = sc.next().toCharArray();
        }
        
        int[][][] dp = new int[n][m][3];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                Arrays.fill(dp[i][j], n*m);
            }
        }
        
        dp[0][0][0] = dp[0][0][1] = dp[0][0][2] = 1;
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(ch[i][j] == '*') continue;
                for(int k = 0; k < 3; k++) {
                    if(i-1 >= 0) {
                        dp[i][j][0] = Math.min(dp[i][j][0], dp[i-1][j][k] + (k != 0 ? 1 : 0));
                    }
                    if(j-1 >= 0) {
                        dp[i][j][1] = Math.min(dp[i][j][1], dp[i][j-1][k] + (k != 1 ? 1 : 0));
                    }
                    if(i-1 >= 0 && j-1 >= 0) {
                        dp[i][j][2] = Math.min(dp[i][j][2], dp[i-1][j-1][k] + (k != 2 ? 1 : 0));
                    }
                }
            }
        }
        
        int ans = Math.min(Math.min(dp[n-1][m-1][0], dp[n-1][m-1][1]), dp[n-1][m-1][2]);
        System.out.println(ans >= n*m ? -1 : ans);
    }
}

n, m = map(int, input().split())
ch = [input() for _ in range(n)]
dp = [[[n*m]*3 for _ in range(m)] for _ in range(n)]

dp[0][0][0] = 1
dp[0][0][1] = 1
dp[0][0][2] = 1

for i in range(n):
    for j in range(m):
        for k in range(3):
            if ch[i][j] == '*':
                continue
            if(i-1>=0):
                dp[i][j][0] = min(dp[i][j][0], dp[i-1][j][k]+int(k!=0))
            if(j-1>=0):
                dp[i][j][1] = min(dp[i][j][1], dp[i][j-1][k]+int(k!=1))
            if(i-1>=0 and j-1>=0):
                dp[i][j][2] = min(dp[i][j][2], dp[i-1][j-1][k]+int(k!=2))

ans = min(dp[n-1][m-1][0], dp[n-1][m-1][1], dp[n-1][m-1][2])

if ans >= n*m:
    print(-1)
else:
    print(ans)

算法及复杂度

算法：动态规划
时间复杂度： $\mathcal{O}(n \cdot m \cdot 3)$ - 需要遍历每个位置的三个方向
空间复杂度： $\mathcal{O}(n \cdot m \cdot 3)$ - 需要三维DP数组存储状态

注意：

需要考虑三个不同的移动方向
改变移动方向时需要增加一步
使用 $n \cdot m$ 作为无穷大值判断无法到达的情况
当无法到达终点时返回 $-1$