I am trying to solve Longest Increasing Path in a grid using DFS in Leetcode using following code.

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

But encountered with following error in 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

NEED HELP!!!!! It is a graph problem. I am using DFS method to solve this. It is 329th problem in Leetcode.

CodePudding user response：

So first problem (did not look deeper) is that call

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

and the use of the variables iniI iniJ without checking the value here:

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

That accesses the array members with a negative index...

CodePudding user response：

Fist of matrix should be const. You are not changing it. And int is the wrong type for an index, use std::size_t. But then you have to change how you check the boundaries.

The way you try to count the length of the path is broken, it's always reset to 0. You need to pass this as an argument, not as a global, or you have to backtrack it in the recursion. You also need to set final inside dfs because as you unravel the recursion the cnt will be lost. Or you can return the length of the tail.

The iniI and initJ are misnamed, they are the last, not the initial, values. You passing -1, -1 leads to an out-of-bounds access to the vector, which gives you the error in the question.

Passing initI and initJ is problematic because on the first call there is no safe value to pass along.

Combining all that why not only recurse when the recursion is valid instead of checking at the start of dfs if it was after the fact?

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

Secondly checking every cell of the matrix is wasteful. Any cell that has a neighbor that is smaller can't be the longest increasing path because starting at that neighbor will be at least 1 longer. That should eliminate a lot of cells and greatly speed up the process.