Matrix bottom left to top right

Question

Can someone please review this simple code for printing all paths in a matrix from bottom left to top right? If an element is 1, it is a "wall" and you cannot take it.

Possible steps: up and right

  // Prints possible paths from bottom left to top right
    public static void findPath(int n, int i , int j, int[][] mat,ArrayList<Integer> path)
    {
        if(i==0 && j==n-1)
        {
            System.out.println();
            for(Integer step: path)
            {
                System.out.print(","+step);
            }
        }

        if(isPossibleStep(i+1,j,n,mat))
        {
            path.add(i+1);
            findPath(n,i+1, j,mat, path);
        }
        else if(isPossibleStep(i,j-1,n,mat))
        {
            path.add(j-1);
            findPath(n,i, j-1,mat, path);
        }

    }

    // Tells if a given path is possible
    public static boolean isPossibleStep(int i, int j, int n,int[][] mat)
    {
        if(mat[i][j]==1)
            return false;

        if(i < n && j > 0)
            return true;
        else
            return false;
    }

Also, how do I print just 1 possible path and then exit? It seems like a simple change but I am not able to think of a graceful way of doing it.

Answer 1

You can refactor the findPath logic somewhat and reduce the indent level while preserving the method's behavior:

// Prints possible paths from bottom left to top right
public static void findPath(int n, int i , int j, int[][] mat, ArrayList<Integer> path)
{
    if(i == 0 && j == n - 1)
    {
        System.out.println();
        for(Integer step: path)
        {
            System.out.print("," + step);
        }
    }

    boolean rightStep = isPossibleStep(i + 1, j, n, mat);                
    if(!isPossibleStep(i, j - 1, n, mat) && !rightStep)
        return;

    path.add(rightStep ? ++i : --j);
    findPath(n, i, j, mat, path);    
}

isPossibleStep can also be simplified by use of short-circuit logic. The following expresses the intent more directly with the benefit of being terse:

public static boolean isPossibleStep(int i, int j, int n, int[][] mat)
{
    return mat[i][j] != 1 
        && i < n 
        && j > 0;
}

Answer 2

I wonder what's the use of adding just i+1 or j-1 to the path. Shouldn't the path be composed of index pairs (i,j)?

Building upon Victor's answer, here are some more optimizations:

public static void findPath(int n, int i, int j, int[][] mat, ArrayList<Integer> path) {
    if (i == 0 && j == n-1) {
        System.out.println(path);    // (1)
    }

    Integer step;    // (2)
    if (isPossibleStep(i + 1, j, n, mat)) {
        step = ++i;
    } else if (isPossibleStep(i, j - 1, n, mat)) {
        step = --j;
    } else {
        return;
    }

    path.add(step);
    findPath(n, i, j, mat, path);
}

public static boolean isPossibleStep(int i, int j, int n, int[][] mat) {
    return i < n && j >= 0    // (3)
        && mat[i][j] != 1;
}

Notes:

1. Instead of looping over the collection to print it, ArrayList's toString() method can do that (with better performance). If you don't want to print the square brackets, just do a substring:

   String pathStr = path.toString();
   System.out.println(pathStr.substring(1, pathStr.length()-1);
   

2. The code surrounding the temporary step variable can be simplified if you use index pairs to represent the path.

3. The method isPossibleStep must check the indices before it tries to access the matrix. Otherwise you could end up with an ArrayIndexOutOfBoundsException. Also note that I'm checking for j >= 0, because 0 is a valid index. (You should also check that i >= 0 && j < n to be safe.)