[数据结构与算法]Leetcode-576 出界的路径数

Leetcode-576 出界的路径数

很长时间没写了，做题倒一直没拉下。但是现在一回顾，发现之前做的题目好多都不会了。还是继续题解吧，不求写题解将全部题目都记住，只是做个记录，以便以后的复习。

题目

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn] 。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn ，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 109 + 7 取余 后的结果。

输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出：6

提示：

• 1 <= m, n <= 50
• 0 <= maxMove <= 50
• 0 <= startRow < m
• 0 <= startColumn < n

解答

方法一 记忆化搜索

一看到这题，嗯，这不很简单嘛，直接一个模拟就完了，仿照搜索将所有可能的情况全部遍历就好了。但很可惜，94 个测试点，连 1/3 都没过，直接卡在第 22 个测试点了。这就需要进行优化了，使用记忆化搜索，将可能的情况进行记录，减少遍历。

class Solution {
public:
    int mod = pow(10, 9) + 7;
    int dirt[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    vector<vector<vector<int>>> vec = vector<vector<vector<int>>>(51, vector<vector<int>>(51, vector<int>(51, -1)));
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        return dfs(m, n, maxMove, startRow, startColumn);
    }

    int dfs(int m, int n, int maxMove, int startRow, int startColumn) {
        if (startRow < 0 || startRow >= m || startColumn < 0 || startColumn >= n)
            return 1;
        if (maxMove == 0)
            return 0;
        if (vec[maxMove][startRow][startColumn] != -1)
            return vec[maxMove][startRow][startColumn];
        int res = 0;
        for (int i = 0; i < 4; i++) {
            int row = startRow + dirt[i][0];
            int colume = startColumn + dirt[i][1];
            res = (res + dfs(m, n, maxMove - 1, row, colume)) % mod;
        }
        vec[maxMove][startRow][startColumn] = res;
        return vec[maxMove][startRow][startColumn];
    }
};

这里有个问题，我不知道如何将 vector 的声明与初始化分开，因此干脆按照提示直接分配了最大的空间。我也试过将 vector 在findPaths() 函数中初始化，将其作为参数带入到 dfs 中，但很可惜，第 12 个测试点都没过，怀疑是函数调用时参数拷贝的锅。

其大致思路是用一个三维数组以坐标和剩余步数为依据记录出界的路径数，当出界时，上一步的出界路径数加一。如果在某坐标剩余步数确定的情况下出界的路径数已经计算完毕，则直接使用即可，无需再次遍历。

方法二 动态规划

其实根据上面的思路，可以发现动态规划的状态由三个维度决定，分别是移动步数、横坐标与纵坐标。创建三维数组vec[i][j][k]，表示移动 i 步后到达坐标 (j, k)。可以想象，当第 i 步到达(j, k)时，由于一开始的出发位置不会出界，因此可以假设当第 i 步到达(j, k)时没有出界。那么下一步也就是移动 i + 1 步后，到达的位置一定与 (j, k) 相邻，假设到达 (j’, k’)。那么此时的可能情况为：

• 出界，那么出界的情况需要加上 vec[i][j][k]。
• 未出界，那么 vec[i + 1][j‘][k’] += vec[i][j][k]。

那么从移动步数为 0 开始遍历，就可以得到移动步数为 maxMove 的情况。

class Solution {
public:
    int mod = pow(10, 9) + 7;
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int ans = 0;
        int dirt[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        vector<vector<vector<int>>> vec(maxMove + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
        vec[0][startRow][startColumn] = 1;
        for (int i = 0; i < maxMove; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    int cnt = vec[i][j][k];
                    if (cnt > 0) {
                        for (int d = 0; d < 4; d++) {
                            int row = j + dirt[d][0];
                            int colume = k + dirt[d][1];
                            if (row < 0 || row >= m || colume < 0 || colume >= n)
                                ans = (ans + cnt) % mod;
                            else 
                                vec[i + 1][row][colume] = (vec[i + 1][row][colume] + cnt) % mod;
                        }
                    }
                }
            }
        }
        return ans;
    }
};