Longest possible route in a matrix with hurdles in Java

Question

I'm working on the following problem:

Given an N x M matrix, with a few hurdles (denoted by 0) arbitrarily placed.

Calculate the length of the longest possible route possible from source (xs, ys) to a destination (xd, yd) within the matrix. We are allowed to move to only adjacent cells which are not hurdles.

The route cannot contain any diagonal moves, and a location once visited in a particular path cannot be visited again.

If it is impossible to reach the destination from the source, return -1.

Example:

Input:

{xs, ys} = {0, 0}
{xd, yd} = {1, 7}

matrix = { {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
           {1, 1, 0, 1, 1, 0, 1, 1, 0, 1},
           {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} }

Output:

24

Explanation:

The problem is that my code is giving me -1 as an output all the time. What could be the reason for that?

My code:

public static int longestPath(int[][] mat, int n, int m, int xs, int ys, int xd, int yd) {
    // code here
    if (mat[xs][ys] == 0 || mat[xd][yd] == 0) {
        return -1;
    }
    
    int ans = -1;
    findLongestPath(mat, n, m, xs, ys, xd, yd, 0, ans);
    return ans;
}

public static void findLongestPath(int[][] mat, int n, int m, int x, int y, int xd, int yd, int pathLength, int ans) {
    if (x == xd && y == yd) {
        ans = Math.max(pathLength, ans);
        return;
        
        //if(pathLength > ans){
        //  ans = pathLength;
        //return;
        //}
    }
    
    if (x < 0 || y < 0 || x >= n || y >= m || mat[x][y] == 2) {
        return;
    }
    
    //visited
    mat[x][y] = 2;
    
    //call neighbours
    findLongestPath(mat, n, m, x + 1, y, xd, yd, pathLength + 1, ans);
    findLongestPath(mat, n, m, x - 1, y, xd, yd, pathLength + 1, ans);
    findLongestPath(mat, n, m, x, y + 1, xd, yd, pathLength + 1, ans);
    findLongestPath(mat, n, m, x, y - 1, xd, yd, pathLength + 1, ans);
    
    mat[x][y] = 1;
}

Answer 1

There are many things should be taken into account while addressing this problem.

Firstly, it seems like you have a misconception regarding Java memory model.

When a method is being called, a new frame is being allocated on the Stack. Local variables (like method arguments) reside on the Stack and their scope is limited to a particular method. When method execution terminates, they vanish. Changing variable ans effects only value in the scope of a particular method invocation, but has no impact on the values of ans in other arias of the Stack.

The simplest way to fix this problem is to make the method return the resulting value instead of being void. Variables pathLength, ans are redundant in this case.

Another important thing to consider while implementing a recursive solution is that every recursive implementation should contain two parts (either explicitly or implicitly): Base case and Recursive case.

Let's have a look at them closely:

• Base case - a part that represents a simple edge-case (or a set of edge-cases), i.e. a situation in which recursion should terminate. The outcome for these edge-cases is known in advance. For this task, edge cases could be combined into two groups:

  • the target cell is reached - current coordinates are equal to target coordinates and return value should be zero (because we are on the target cell and cells can't be visited twice);
  • a situation when the current cell should be considered to be an invalid one. There could be three causes: invalid coordinates, the cell has been already visited, or the current cell contains an obstacle (i.e. array element hold a value of 0). Return value should be -1 (path through this cell doesn't exist).

• Recursive case - is the part of the method where recursive calls are made and where the main logic resides. Every recursive call eventually hits the base case and the process of accumulating the return value begins.

In the recursive case, we need to check the paths through all adjacent cells of this cell and pick the maximum value. If maximum equals to -1 (i.e. it's not possible to reach the target cell from this cell), then the return value in the recursive case should be -1 as well. Otherwise (if the path exist), we should return maximum path +1 because maximum path represents the length of the path from one of the adjacent cells to the target cell but not from the current one. And the length of the path from the current cell to an adjacent cell is 1.

Also note that naming is also important for understanding of the code and avoiding mistakes. I deliberately used row and col to refer to a row and column of a particular "cell" (element of the nested array) instead of x and y. When you refer to an element in the nested array firstly you need to specify the subarray, and then position in the subarray (i.e. mat[row][col] or mat[y][x]). If you look carefully at your code, you'll find out that you're doing the opposite (mat[x][y]) because it's more intuitive to specify the x first and then y, but in this case it would be wrong.

That's how implementation might look like:

public static int findLongestPath(int[][] mat, int n, int m,
                                  int row, int col, int rowDest, int colDest) {
    // Base cases

    if (row < 0 || col < 0 || row >= n || col >= m || // invalid coordinate
        mat[row][col] == 2 ||                         // the cell has been visited
        mat[row][col] == 0) {                         // current cell contains an obstacle
        
        return -1;
    }
    
    if (row == rowDest && col == colDest) return 0; // the target cell is reached

    // Recursive case

    mat[row][col] = 2; // marking the current cell as visited
    
    // calling the neighbors
    int right = findLongestPath(mat, n, m, row + 1, col, rowDest, colDest);
    int left = findLongestPath(mat, n, m, row - 1, col, rowDest, colDest);
    int top = findLongestPath(mat, n, m, row, col + 1, rowDest, colDest);
    int bottom = findLongestPath(mat, n, m, row, col - 1, rowDest, colDest);

    mat[row][col] = 1; // restoring the previous value

    int max = Math.max(Math.max(left, right), Math.max(top, bottom));

    return max == -1 ? -1 : max + 1;
}

main()

public static void main(String[] args) {
    
    int[][] matrix1 = {
        {1, 0, 1},
        {1, 1, 1},
        {0, 1, 1}
    };
    
    System.out.println(findLongestPath(matrix1, 3, 3, 0, 0, 0, 2));

    int[][] matrix2 = { {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                        {1, 1, 0, 1, 1, 0, 1, 1, 0, 1},
                        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1} };

    System.out.println(findLongestPath(matrix2, 3, 10, 0, 0, 1, 7));
}

Output:

6
24