题解 | 红魔馆的走廊清理

#include <algorithm>
#include <cmath>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> puzz(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> puzz[i][j];
        }
    }
    if (m <= 0 || m > 100 || n <= 0 || n >100) {
        cout << -1;
        return 0;
    }
    vector<vector<pair<int, int>>> dp(m, vector<pair<int, int>>(n, {-1, -1}));
    dp[0][0] = {0, 0};
    for (int i = 1; i < m; i++) 
        if (puzz[i][0] == 0)
            dp[i][0].second = 0;
        else break;
    for (int j = 1; j < n; j++)
        if (puzz[0][j] == 0)
            dp[0][j].first = 0;
        else break;
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            if (puzz[i][j] == 0) {
                if (dp[i][j - 1].first != -1 && dp[i][j - 1].second != -1)
                    dp[i][j].first = min(dp[i][j - 1].first, dp[i][j - 1].second + 1);
                if (dp[i][j - 1].first == -1 && dp[i][j - 1].second != -1)
                    dp[i][j].first = dp[i][j - 1].second + 1;
                if (dp[i][j - 1].first != -1 && dp[i][j - 1].second == -1)
                    dp[i][j].first = dp[i][j - 1].first;
                if (dp[i - 1][j].first != -1 && dp[i - 1][j].second != -1)
                    dp[i][j].second = min(dp[i - 1][j].first + 1, dp[i - 1][j].second);
                if (dp[i - 1][j].first == -1 && dp[i - 1][j].second != -1)
                    dp[i][j].second = dp[i - 1][j].second;
                if (dp[i - 1][j].first != -1 && dp[i - 1][j].second == -1)
                    dp[i][j].second = dp[i - 1][j].first + 1;
            }   
        }
    }
    // for (int i = 0; i < m; i++) {
    //     for (int j = 0; j < n; j++) {
    //         cout << '(' << dp[i][j].first << ',' << dp[i][j].second << ") ";
    //     }
    //     cout << endl;
    // }
    int ans;
    if (dp[m - 1][n - 1].first != -1 && dp[m - 1][n - 1].second != -1) ans = min(dp[m - 1][n - 1].first, dp[m - 1][n - 1].second);
    else if (dp[m - 1][n - 1].first == -1) ans = dp[m - 1][n - 1].second;
    else if (dp[m - 1][n - 1].second == -1) ans = dp[m - 1][n - 1].first;
    else ans = -1;
    cout << ans;
    return 0;
}
// 64 位输出请用 printf("%lld")

动态规划五部曲

1. 确定 dp 数组的下标及含义

2维 dp 数组，dp[i][j] 对应 puzz[i][j]，用 pair ，first 代表从左边的节点向右得到时的最小转弯次数，second 代表从上边的节点向下得到时的最小转弯次数，初始化为 -1 表示不可达

vector<vector<pair<int, int>>> dp(m, vector<pair<int, int>>(n, {-1, -1}));

2. 确定递推公式

puzz[i][j] == 0 时，才有可能是可达的。

• (i,j) 从左边推得时，先判断左边的元素 (i,j-1) 是否从左和上可达，都可达取左边节点从左来的转弯次数和从上来的转弯次数+1的最小值，其中一边可达取对应的，都不可达 (i,j) 从左边也是不可达的，不用处理。
• (i,j) 从上边推得时，先判断上边的元素 (i-1,j) 是否从左和上可达，都可达取左边节点从左来的转弯次数+1和从上来的转弯次数的最小值，其中一边可达取对应的，都不可达 (i,j) 从上边也是不可达的，不用处理。

if (puzz[i][j] == 0) {
    // 左
    if (dp[i][j - 1].first != -1 && dp[i][j - 1].second != -1)
        dp[i][j].first = min(dp[i][j - 1].first, dp[i][j - 1].second + 1);
    if (dp[i][j - 1].first == -1 && dp[i][j - 1].second != -1)
        dp[i][j].first = dp[i][j - 1].second + 1;
    if (dp[i][j - 1].first != -1 && dp[i][j - 1].second == -1)
        dp[i][j].first = dp[i][j - 1].first;
    // 上
    if (dp[i - 1][j].first != -1 && dp[i - 1][j].second != -1)
        dp[i][j].second = min(dp[i - 1][j].first + 1, dp[i - 1][j].second);
    if (dp[i - 1][j].first == -1 && dp[i - 1][j].second != -1)
        dp[i][j].second = dp[i - 1][j].second;
    if (dp[i - 1][j].first != -1 && dp[i - 1][j].second == -1)
        dp[i][j].second = dp[i - 1][j].first + 1;
}

3. dp 数组的初始化

• 起点应初始化为0表示可达，还没开始走，转弯次数是0
• 第1行，第1列的元素从 (0,0) 开始遍历，puzz[i][j] 是0可达，转弯次数为0，遇到 puzz[i][j] 不为0就停，这里以及后面的都不可达，不用处理了

dp[0][0] = {0, 0};
for (int i = 1; i < m; i++) 
    if (puzz[i][0] == 0)
        dp[i][0].second = 0;
    else break;
for (int j = 1; j < n; j++)
    if (puzz[0][j] == 0)
        dp[0][j].first = 0;
    else break;

4. 确定遍历顺序

dp[i][j] 依赖于 dp[i - 1][j] 和 dp[i][j - 1]，所以从上到下从左到右遍历矩阵即可

5. 举例推导 dp 数组

推导出示例的 dp 数组如下

(0,0) (-1,-1) (-1,-1)

(-1,0) (1,-1) (1,-1)

(-1,-1) (-1,2) (3,2)

符合题意，终点(2,2)从左和上都可达，取最小值为2正确。

性能分析

1. 时间复杂度

输入：O(m * n)

遍历求 dp[i][j]：O(m * n)

2. 空间复杂度

使用额外空间 dp 数组：O(m * n)