# 134. 皇后移动的最小步数

题目链接 (opens new window)

本题和代码随想录-不同路径 (opens new window) 有一些类似。

关键是弄清楚递推公式

一共分三个情况，

情况一，向右移动：

然后从 (i, j) 再向右走到 (i, k)。无论k 多大，步数只加1 ：

dp[i][k] = dp[i][j] + 1

那么 dp[i][k] 也有可能从其他方向得到，例如从上到下，或者斜上方到达 dp[i][k]

本题我们要求最小步数，所以取最小值：dp[i][k] = min(dp[i][k], dp[i][j] + 1);

情况二，向下移动：

从 (i, j) 再向下走到 (k, j)。无论k 多大，步数只加1 ：

dp[k][j] = dp[i][j] + 1;

同理 dp[i][k] 也有可能从其他方向得到，取最小值：dp[k][j] = min(dp[k][j], dp[i][j] + 1);

情况三，右下方移动：

从 (i, j) 再向右下方移动到 (i + k, j + k)。无论k 多大，步数只加1 ：

dp[i + k][j + k] = dp[i][j] + 1

同理 dp[i + k][j + k] 也有可能从其他方向得到，取最小值：dp[i + k][j + k] = min(dp[i + k][j + k], dp[i][j] + 1);

#include <iostream>
#include <vector>
using namespace std;
const int INF = 4e6; // 最多步数也就是 2000 * 2000
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<char>> grid(n, vector<char>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }
    vector<vector<int>> dp(n, vector<int>(m, INF));
    dp[0][0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '*') continue;
            // 向右移动k个格子
            for (int k = j + 1; k < m && grid[i][k] == '.'; k++) {
                dp[i][k] = min(dp[i][k], dp[i][j] + 1);
            }
            // 向下移动 k个格子
            for (int k = i + 1; k < n && grid[k][j] == '.'; k++) {
                dp[k][j] = min(dp[k][j], dp[i][j] + 1);
            }
            // 向右下移动k个格子
            for (int k = 1; i + k < n && j + k < m && grid[i + k][j + k] == '.'; k++) {
                dp[i + k][j + k] = min(dp[i + k][j + k], dp[i][j] + 1);
            }
        }
    }
    if (dp[n - 1][m - 1] == INF) cout << -1 << endl;
    else cout << dp[n - 1][m - 1] << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35