题解 | #小红的皇后#

题目链接

小红的皇后

题目描述

在一个 $n \times m$ 的棋盘上，小红的皇后从左上角 (0,0) 出发，要到达右下角 (n-1, m-1)。有些格子是障碍物。

皇后每次可以向右、下或右下移动任意多个格子，但移动的路径上不能有障碍物。求从起点到终点的最少移动次数。如果无法到达，输出 -1。

解题思路

这是一个在网格上的最短路径问题。由于每次移动的成本都是 1，且移动距离不固定，使用传统的广度优先搜索（BFS）效率不高。这个问题更适合采用动态规划 (DP) 并进行优化。

1. DP 状态定义

我们定义 dp[i][j] 为皇后到达格子 (i, j) 所需的最少移动次数。我们的最终目标是 dp[n-1][m-1]。

2. DP 状态转移

要到达格子 (i, j)，皇后必然是从其左方、上方或左上方的某个格子一步移动过来的。因此，dp[i][j] 的值等于 1 + min(所有合法来源格子的 dp 值)。

直接枚举所有来源格子会导致超时。我们可以优化这个过程。到达 (i, j) 的来源可以分为三类：

水平来源：来自 (i, k)，其中 $k < j$ 。
垂直来源：来自 (k, j)，其中 $k < i$ 。
对角来源：来自 (i-k, j-k)，其中 $k > 0$ 。

为了 $O(1)$ 地完成转移，我们需要快速知道这三个方向上的 dp 最小值。

3. 优化方法：维护运行最小值

我们可以在遍历棋盘的过程中，维护三个辅助数据结构，用于记录到当前位置为止，各个方向上的 dp 最小值：

一个变量 min_row：记录当前行到 j-1 列为止的 dp 最小值。
一个数组 min_col[m]：min_col[j] 记录第 j 列到 i-1 行为止的 dp 最小值。
一个数组 min_diag[n+m]：min_diag[k] 记录第 k 条对角线（可以用 i-j 区分）到 (i-1, j-1) 为止的 dp 最小值。

4. 算法流程

初始化 dp 表为无穷大，min_col 和 min_diag 数组也为无穷大。
设置起点 dp[0][0] = 0。
从 i = 0到n-1，j = 0到m-1 遍历棋盘。
在内层循环开始前，初始化当前行的 min_row 为无穷大。
如果 grid[i][j] 是障碍物：
- 它会阻断所有经过它的路径。因此，我们将 min_row, min_col[j], min_diag[i-j] 全部重置为无穷大，然后继续下一个循环。
如果 grid[i][j] 是空地：
- 从 min_row, min_col[j], min_diag[i-j] 中找到最小值 min_source。
- 如果 min_source 不是无穷大，则 dp[i][j] = 1 + min_source。
- 特别处理起点：dp[0][0] 始终为 0。
- 计算出 dp[i][j] 后，用它来更新 min_row, min_col[j], 和 min_diag[i-j]，使它们保持为到当前位置为止的最小值。
遍历结束后，如果 dp[n-1][m-1] 是无穷大，则无法到达，输出 -1，否则输出 dp[n-1][m-1]。

代码

cpp
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 (grid[0][0] == '*' || grid[n - 1][m - 1] == '*') {
        cout << -1 << endl;
        return 0;
    }

    vector<vector<int>> dp(n, vector<int>(m, INF));
    vector<int> min_col(m, INF);
    vector<int> min_diag(n + m, INF);

    dp[0][0] = 0;

    for (int i = 0; i < n; ++i) {
        int min_row = INF;
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == '*') {
                min_row = INF;
                min_col[j] = INF;
                min_diag[i - j + m - 1] = INF;
                continue;
            }

            int min_source = min({min_row, min_col[j], min_diag[i - j + m - 1]});

            if (i == 0 && j == 0) {
                 dp[i][j] = 0;
            } else if (min_source != INF) {
                dp[i][j] = 1 + min_source;
            }

            if (dp[i][j] != INF) {
                min_row = min(min_row, dp[i][j]);
                min_col[j] = min(min_col[j], dp[i][j]);
                min_diag[i - j + m - 1] = min(min_diag[i - j + m - 1], dp[i][j]);
            }
        }
    }

    if (dp[n - 1][m - 1] == INF) {
        cout << -1 << endl;
    } else {
        cout << dp[n - 1][m - 1] << 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 (grid[0][0] == '*' || grid[n - 1][m - 1] == '*') {
            System.out.println(-1);
            return;
        }

        int INF = Integer.MAX_VALUE / 2;
        int[][] dp = new int[n][m];
        for (int[] row : dp) Arrays.fill(row, INF);
        
        int[] minCol = new int[m];
        Arrays.fill(minCol, INF);
        
        int[] minDiag = new int[n + m];
        Arrays.fill(minDiag, INF);
        
        dp[0][0] = 0;

        for (int i = 0; i < n; i++) {
            int minRow = INF;
            for (int j = 0; j < m; j++) {
                int diagIndex = i - j + m - 1;

                if (grid[i][j] == '*') {
                    minRow = INF;
                    minCol[j] = INF;
                    minDiag[diagIndex] = INF;
                    continue;
                }
                
                int minSource = Math.min(minRow, Math.min(minCol[j], minDiag[diagIndex]));

                if (i == 0 && j == 0) {
                    dp[i][j] = 0;
                } else if (minSource != INF) {
                    dp[i][j] = 1 + minSource;
                }

                if (dp[i][j] != INF) {
                    minRow = Math.min(minRow, dp[i][j]);
                    minCol[j] = Math.min(minCol[j], dp[i][j]);
                    minDiag[diagIndex] = Math.min(minDiag[diagIndex], dp[i][j]);
                }
            }
        }

        if (dp[n - 1][m - 1] == INF) {
            System.out.println(-1);
        } else {
            System.out.println(dp[n - 1][m - 1]);
        }
    }
}

import sys

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

    if grid[0][0] == '*' or grid[n - 1][m - 1] == '*':
        print(-1)
        return

    INF = float('inf')
    dp = [[INF] * m for _ in range(n)]
    min_col = [INF] * m
    min_diag = [INF] * (n + m)
    
    dp[0][0] = 0

    for i in range(n):
        min_row = INF
        for j in range(m):
            diag_index = i - j + m - 1

            if grid[i][j] == '*':
                min_row = INF
                min_col[j] = INF
                min_diag[diag_index] = INF
                continue

            min_source = min(min_row, min_col[j], min_diag[diag_index])

            if i == 0 and j == 0:
                dp[i][j] = 0
            elif min_source != INF:
                dp[i][j] = 1 + min_source

            if dp[i][j] != INF:
                min_row = min(min_row, dp[i][j])
                min_col[j] = min(min_col[j], dp[i][j])
                min_diag[diag_index] = min(min_diag[diag_index], dp[i][j])

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

solve()

算法及复杂度

算法：动态规划
时间复杂度： $O(N \cdot M)$ 。
- 我们对 $N \times M$ 的棋盘进行一次遍历，每次遍历中的操作都是常数时间的。
空间复杂度： $O(N \cdot M)$ 。
- 主要空间开销是 dp 数组。辅助数组 min_col 和 min_diag 的大小为 $O(M+N)$ 。