C++基于DFS求解LeetCode329最长递增路径时触发RTE求助

在LeetCode使用C++以DFS思路求解第329题《网格中的最长递增路径》时，提交代码触发未定义行为类运行时错误，原实现代码如下：

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;
}
};

运行时抛出的错误信息：

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时传入的上一节点坐标为iniI=-1、iniJ=-1，代码仅校验了当前坐标i,j的边界，未校验iniI,iniJ的有效性就直接访问matrix[iniI][iniJ]。vector的下标运算符使用无符号类型计算偏移，负数索引会被转换为极大的无符号整数值，直接访问非法内存地址，这就是报错中提到的偏移溢出问题。
• 路径计数逻辑失效：全局变量cnt每次进入DFS函数都会被重置为0，完全无法累计递归过程中的路径长度；且DFS函数无返回值，无法记录从当前节点出发可延伸的最长路径长度，即使修复越界问题也无法算出正确结果。
• 无记忆化优化：纯暴力DFS会重复遍历大量重复子路径，在网格尺寸稍大的测试用例下会直接超时。

调整DFS逻辑，增加记忆化缓存存储每个节点已经计算出的最长路径长度，移除全局计数变量，严格按照先校验坐标边界、再判断路径递增性的顺序写递归逻辑，修正后的可运行代码如下：

class Solution {
private:
    // 上下左右四个方向的坐标偏移
    int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    int dfs(int i, int j, vector<vector<int>>& matrix, vector<vector<int>>& memo) {
        // 命中缓存直接返回预计算结果
        if (memo[i][j] != 0) return memo[i][j];
        int maxPath = 1;
        for (auto& dir : dirs) {
            int nextI = i + dir[0];
            int nextJ = j + dir[1];
            // 先校验新坐标合法性，再判断是否满足递增要求
            if (nextI >= 0 && nextI < matrix.size() && nextJ >=0 && nextJ < matrix[0].size() && matrix[nextI][nextJ] > matrix[i][j]) {
                int curPath = 1 + dfs(nextI, nextJ, matrix, memo);
                maxPath = max(maxPath, curPath);
            }
        }
        memo[i][j] = maxPath;
        return maxPath;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        // memo[i][j]存储从坐标(i,j)出发的最长递增路径长度
        vector<vector<int>> memo(m, vector<int>(n, 0));
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                res = max(res, dfs(i, j, matrix, memo));
            }
        }
        return res;
    }
};

内容的提问来源于stack exchange，提问作者Ahamad Mamun Nishar Miya