CODEWITHSUNDEEP
javamatrix
gxxgly_eyez
gxxgly_eyez

Reputation: 41

Finding a path in a matrix in recursion

I'm trying to solve a problem in a course that I am taking, finding the longest path in a matrix that contains numbers - with a specific difference between the numbers.

I have private methods that check in which direction I can do, but now I am trying to find the "depth" of the slope.

I am keeping a maxDepth variable for each dive - and assigning it to "depth" if it's the deepest - for some reason, depth remains at 0 all the time.

private static int longestSlope(int[][] mat, int num, int i, int j, int depth, int maxDepth ){
        if (canUp(mat, num, i, j)) {
            maxDepth = longestSlope(mat, num, i - 1, j, depth, maxDepth + 1);
            if (depth < maxDepth) {
                depth = maxDepth;
            }
            maxDepth = 0;
        }
        if (canDown(mat, num, i, j)) {
            maxDepth = longestSlope(mat, num, i + 1, j, depth, maxDepth + 1);
            if (depth < maxDepth) depth = maxDepth;
            maxDepth = 0;
        }
        if (canRight(mat, num, i, j)) {
            maxDepth = longestSlope(mat, num, i, j + 1, depth, maxDepth + 1);
            if (depth < maxDepth) depth = maxDepth;
            maxDepth = 0;
        }
        if (canLeft(mat, num, i, j)) {
            maxDepth = longestSlope(mat, num, i, j - 1, depth, maxDepth + 1);
            if (depth < maxDepth) depth = maxDepth;
        }

        return depth;
    }


private static boolean canUp(int[][] mat, int num, int i, int j) {
    if (i == 0) {
        return false;
    } else if (mat[i - 1][j] == -1) {
        return false;
    } else if (mat[i][j] - mat[i - 1][j] != num) {
        return false;
    }
    return true;
}

Screenshot from IntelliJ

Upvotes: 0

Views: 503

Answers (1)

Anshuman Dikhit
Anshuman Dikhit

Reputation: 459

You are returning depth after checking whether you can move in each direction. This will cause a problem for you when you reach a point where you cannot move in any direction. Since depth is updated after the recursive call, your method would return 0 and that value would be assigned to maxDepth in its parent recursive call. You want to have a base case check for when you reach a point where you cannot move in any of the 4 directions. Something like this should do the trick:

private static int longestSlope(int[][] mat, int num, int i, int j, int depth, int maxDepth ){
    if(canUp(mat, num, i, j) == false && canDown(mat, num, i, j) == false && canRight(mat, num, i, j) == false) && canDown(mat, num, i, j) == false) {
        // this means that you cannot move in any of the 4 directions: the base case
        return maxDepth;
    }
    if (canUp(mat, num, i, j)) {
        maxDepth = longestSlope(mat, num, i - 1, j, depth, maxDepth + 1);
        if (depth < maxDepth) {
            depth = maxDepth;
        }
        maxDepth = 0;
    }
    if (canDown(mat, num, i, j)) {
        maxDepth = longestSlope(mat, num, i + 1, j, depth, maxDepth + 1);
        if (depth < maxDepth) depth = maxDepth;
        maxDepth = 0;
    }
    if (canRight(mat, num, i, j)) {
        maxDepth = longestSlope(mat, num, i, j + 1, depth, maxDepth + 1);
        if (depth < maxDepth) depth = maxDepth;
        maxDepth = 0;
    }
    if (canLeft(mat, num, i, j)) {
        maxDepth = longestSlope(mat, num, i, j - 1, depth, maxDepth + 1);
        if (depth < maxDepth) depth = maxDepth;
    } 
    return depth;
}

For future reference, it's always a good idea to determine what your base case is in a recursive function, and to return whatever value it is you are calculating. Doing so will help you avoid such subtle bugs!

Upvotes: 2

Related Questions