用C++和RTE解决Leetcode的“网格中最长增长路径”

Question

我试图用下面的代码解决网格中最长的增长路径，在Leetcode中使用DFS。

class Solution {
public:
int cnt = 0;


void dfs(int i, int j, int iniI, int iniJ, vector<vector<int>>& matrix){

    cnt = 0;
    if(i >= matrix.size() || j >= matrix[0].size()) return;
    if(i < 0 || j < 0) return;
    if(matrix[i][j] <= matrix[iniI][iniJ]) return;



    cnt++;

    dfs(i + 1, j, i, j, matrix);
    dfs(i - 1, j, i, j, matrix);
    dfs(i, j + 1, i, j, matrix);
    dfs(i, j - 1, i, j, matrix);

    return;

}




int longestIncreasingPath(vector<vector<int>>& matrix) {
    int final = 0;
        for (int i = 0; i < matrix.size(); ++i)
        {
            for (int j = 0; j < matrix[0].size(); ++j)
            {
                dfs(i, j, -1, -1, matrix);
                final = max(final, cnt);
            }
        }
        return final;
}
};

但在Leetcode中遇到了以下错误。

Line 1034: Char 34: runtime error: addition of unsigned offset to 0x608000000020 overflowed to 0x608000000008 (stl_vector.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

需要帮助！这是一个图问题。我正在使用DFS方法来解决这个问题。这是Leetcode中的329个问题。

Answer 1

所以第一个问题(没有看得更深)是那个电话。

dfs(i, j, -1, -1, matrix)

以及在这里使用变量iniI iniJ而不检查值：

if(matrix[i][j] <= matrix[iniI][iniJ]) return; 

它使用负索引访问数组成员.

Answer 2

matrix的第一名应该是康斯特。你不能改变它。而int是索引的错误类型，请使用std::size_t。但是你必须改变你检查边界的方式。

您试图计算路径长度的方式被破坏了，它总是被重置为0。您需要将它作为参数传递，而不是作为全局参数传递，或者您必须在递归中回溯它。您还需要在final中设置dfs，因为当您解开递归时，cnt将丢失。或者你可以返回尾巴的长度。

iniI和initJ被错误命名，它们是最后的值，而不是初始值。通过-1, -1将导致对向量的越界访问，这将给出问题中的错误。

传递initI和initJ是有问题的，因为在第一次调用时，没有安全的值可以传递。

综合所有这些，为什么不仅在递归有效的情况下进行递归，而不是在dfs开始时进行检查(如果是事后检查)？

std::size_t dfs(std::size_t i, std::size_t j, const vector<vector<int>>& matrix){
    std::size_t cnt = 0;
    int current = matrix[i][j];

    if ((i + 1 < matrix.size()) && (matrix[i + 1][j] > current))
        cnt = dfs(i + 1, j, matrix);
    if ((i > 0) && (matrix[i -1][j] > current))
        cnt = max(cnt, dfs(i - 1, j, matrix));
    if ((j + 1 < matrix[0].size()) && (matrix[i][j + 1] > current))
        cnt = max(cnt, dfs(i, j + 1, matrix));
    if (j > 0) && (matrix[i][j - 1] > current))
        cnt = max(cnt, dfs(i, j - 1, matrix));

    return cnt + 1;
}

其次，检查矩阵中的每个单元是浪费的。任何具有较小邻居的单元都不可能是最长的增长路径，因为从该邻居开始的时间至少要长1。这将消除大量细胞，并大大加快这一过程。