尝试使用 DFS 解决 Leetcode 的"Longest Increasing Path in a Grid"，但 RTE C++

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的first应为const。你不能改变它。而int是一个错误的索引类型，用std::size_t。但是你必须改变你检查边界的方式。

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

iniI和initJ命名错误，它们是最后一个值，而不是初始值。传递-1, -1将导致对vector的越界访问，从而导致问题中的错误。

传递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倍。这将消除大量细胞，并大大加快这一过程。