题解 | #小红的皇后#

题目链接

题目描述

在一个 $N \times M$ 的棋盘上，有一些格子是障碍物(*)，其余为空格(.)。一个皇后从左上角 $(0,0)$ 出发，目标是到达右下角 $(N-1, M-1)$ 。皇后每次移动可以沿右、下、右下三个方向之一前进任意多格，且移动路径上不能有障碍物。求从起点到终点的最少移动步数。

解题思路

本题可以看作一个最短路径问题，但由于边的权重特殊（每次移动，无论多远，成本都是1），使用动态规划是解决此类问题的经典方法。

核心思想

问题的核心在于，沿同一个方向连续移动不增加步数，但转换方向则需要增加一步。这启发我们，DP的状态不仅要记录位置，还必须记录是“通过哪种方向的移动”到达该位置的。

动态规划设计

状态定义: $dp[i][j][k]$ 表示到达格子 $(i, j)$ 所需的最少移动步数，其中 $k$ 代表最后一步移动的方向：
- $k=0$ : 最后一步是向下移动。
- $k=1$ : 最后一步是向右移动。
- $k=2$ : 最后一步是向右下移动。
状态转移: 对于一个非障碍格子 $(i, j)$ ，我们分别计算 $dp[i][j][0]$ , $dp[i][j][1]$ , $dp[i][j][2]$ 的值。
- 计算 $dp[i][j][0]$ (向下到达): 我们必然是从 $(i-1, j)$ 移动过来的。
  - 情况一：延续向下的移动。如果到达 $(i-1, j)$ 的最后一步也是向下的，我们可以直接延伸这条路径，步数不变。成本为 $dp[i-1][j][0]$ 。
  - 情况二：从 $(i-1, j)$ 开始一次新的向下移动。如果到达 $(i-1, j)$ 的最后一步是向右或向右下，那么从 $(i-1, j)$ 到 $(i, j)$ 就必须开始一次新的移动，步数加 1。成本为 $\min(dp[i-1][j][1], dp[i-1][j][2]) + 1$ 。
  - 综合起来： $dp[i][j][0] = \min(dp[i-1][j][0], \min(dp[i-1][j][1], dp[i-1][j][2]) + 1)$ 。
- 计算 $dp[i][j][1]$ (向右到达): 同理，我们从 $(i, j-1)$ 移动过来。
  - $dp[i][j][1] = \min(dp[i][j-1][1], \min(dp[i][j-1][0], dp[i][j-1][2]) + 1)$ 。
- 计算 $dp[i][j][2]$ (向右下到达): 同理，我们从 $(i-1, j-1)$ 移动过来。
  - $dp[i][j][2] = \min(dp[i-1][j-1][2], \min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + 1)$ 。
初始化:
- 将整个 $dp$ 数组初始化为一个极大值（代表不可达）。
- 对于起点 $(0, 0)$ ，我们定义到达它需要 1 步（即第一步）。所以，如果 grid[0][0] 不是障碍物，我们设置 $dp[0][0][0] = 1, dp[0][0][1] = 1, dp[0][0][2] = 1$ 。这表示从起点可以开始任意方向的移动，成本都是 1。
- 如果 $N=1, M=1$ ，起点即终点，步数为 0，需要特判。
最终答案: 遍历完所有格子后，终点 $(N-1, M-1)$ 的最少步数就是三种方式到达它的步数中的最小值： $\min(dp[N-1][M-1][0], dp[N-1][M-1][1], dp[N-1][M-1][2])$ 。如果这个值仍然是极大值，则说明终点不可达。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    if (n == 1 && m == 1) {
        cout << 0 << endl;
        return 0;
    }

    vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(3, INF)));

    if (grid[0][0] == '.') {
        dp[0][0][0] = 1;
        dp[0][0][1] = 1;
        dp[0][0][2] = 1;
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '*') {
                continue;
            }

            if (i > 0 && grid[i-1][j] == '.') {
                int cost = min(dp[i-1][j][0], min(dp[i-1][j][1], dp[i-1][j][2]) + 1);
                dp[i][j][0] = min(dp[i][j][0], cost);
            }
            if (j > 0 && grid[i][j-1] == '.') {
                int cost = min(dp[i][j-1][1], min(dp[i][j-1][0], dp[i][j-1][2]) + 1);
                dp[i][j][1] = min(dp[i][j][1], cost);
            }
            if (i > 0 && j > 0 && grid[i-1][j-1] == '.') {
                int cost = min(dp[i-1][j-1][2], min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + 1);
                dp[i][j][2] = min(dp[i][j][2], cost);
            }
        }
    }

    int ans = min({dp[n-1][m-1][0], dp[n-1][m-1][1], dp[n-1][m-1][2]});

    if (ans >= INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] grid = new char[n][m];
        for (int i = 0; i < n; i++) {
            grid[i] = sc.next().toCharArray();
        }

        if (n == 1 && m == 1) {
            System.out.println(0);
            return;
        }

        final int INF = 1_000_000_000;
        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], INF);
            }
        }

        if (grid[0][0] == '.') {
            dp[0][0][0] = 1;
            dp[0][0][1] = 1;
            dp[0][0][2] = 1;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '*') {
                    continue;
                }

                if (i > 0 && grid[i - 1][j] == '.') {
                    int cost = Math.min(dp[i-1][j][0], Math.min(dp[i-1][j][1], dp[i-1][j][2]) + 1);
                    dp[i][j][0] = Math.min(dp[i][j][0], cost);
                }
                if (j > 0 && grid[i][j - 1] == '.') {
                    int cost = Math.min(dp[i][j-1][1], Math.min(dp[i][j-1][0], dp[i][j-1][2]) + 1);
                    dp[i][j][1] = Math.min(dp[i][j][1], cost);
                }
                if (i > 0 && j > 0 && grid[i - 1][j - 1] == '.') {
                    int cost = Math.min(dp[i-1][j-1][2], Math.min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + 1);
                    dp[i][j][2] = Math.min(dp[i][j][2], cost);
                }
            }
        }

        int ans = Math.min(dp[n - 1][m - 1][0], Math.min(dp[n - 1][m - 1][1], dp[n - 1][m - 1][2]));

        if (ans >= INF) {
            System.out.println(-1);
        } else {
            System.out.println(ans);
        }
    }
}

import sys

def solve():
    n, m = map(int, sys.stdin.readline().split())
    grid = [sys.stdin.readline().strip() for _ in range(n)]

    if n == 1 and m == 1:
        print(0)
        return

    INF = float('inf')
    # dp[i][j][k] k=0:Down, k=1:Right, k=2:Right-Down
    dp = [[[INF] * 3 for _ in range(m)] for _ in range(n)]

    if grid[0][0] == '.':
        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):
            if grid[i][j] == '*':
                continue

            # Arriving from Above (Down move)
            if i > 0 and grid[i - 1][j] == '.':
                cost = min(dp[i-1][j][0], min(dp[i-1][j][1], dp[i-1][j][2]) + 1)
                dp[i][j][0] = min(dp[i][j][0], cost)
            
            # Arriving from Left (Right move)
            if j > 0 and grid[i][j - 1] == '.':
                cost = min(dp[i][j-1][1], min(dp[i][j-1][0], dp[i][j-1][2]) + 1)
                dp[i][j][1] = min(dp[i][j][1], cost)

            # Arriving from Top-Left (Right-Down move)
            if i > 0 and j > 0 and grid[i - 1][j - 1] == '.':
                cost = min(dp[i-1][j-1][2], min(dp[i-1][j-1][0], dp[i-1][j-1][1]) + 1)
                dp[i][j][2] = min(dp[i][j][2], cost)

    ans = min(dp[n-1][m-1])
    
    if ans == INF:
        print(-1)
    else:
        print(ans)

solve()

算法及复杂度

算法：动态规划 (DP)
时间复杂度： $\mathcal{O}(N \cdot M)$ 。
- 我们需要遍历整个 $N \times M$ 的棋盘。在每个格子，我们执行常数次的状态转移计算。因此，总时间复杂度为 $\mathcal{O}(N \cdot M)$ 。
空间复杂度： $\mathcal{O}(N \cdot M)$ 。
- 主要的空间开销来自于存储状态的 $dp$ 数组，其大小为 $N \times M \times 3$ 。
- 优化提示：由于 $dp[i][j]$ 的计算只依赖于 $dp[i][j-1]$ , $dp[i-1][j]$ 和 $dp[i-1][j-1]$ ，可以使用滚动数组或只保留前一行和当前行的状态，将空间复杂度优化到 $\mathcal{O}(M)$ 。