Count possible paths through a maze

Question

You have to find a path through which the rat move from the starting position (0,0) to the final position where cheese is (n,n). List the total no of possible paths which the rat can take to reach the cheese.

Sample Input:

7

0 0 1 0 0 1 0

1 0 1 1 0 0 0

0 0 0 0 1 0 1

1 0 1 0 0 0 0

1 0 1 1 0 1 0

1 0 0 0 0 1 0

1 1 1 1 0 0 0

Sample Output:

4

My code:

import java.util.*;


class maze

{

    static int n;
    static int[][] a;
    static int path;

    public static void main(String[] ar)
    {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a = new int[n][n];
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                a[i][j] = sc.nextInt();
            }
        }
        search(0,0);
        System.out.println(path);
    }

    public static void search(int i, int j)
    {
        if(!exist(i,j) || a[i][j] == 1)
            return;
        if(i == n-1 && j == n-1)
        {
            path++;
            return;
        }
        a[i][j] = 1;
        search(i+1,j);
        search(i-1,j);
        search(i,j+1);
        search(i,j-1);
        a[i][j] = 0;
    }

    public static boolean exist(int i, int j)
    {
        return i>=0 && j >=0 && i < n && j < n;
    }
}

Can anybody recommend a better solution than this or if there are any, please point out the mistakes in this. I made it using simple logic and I don't know much about graph theory. Is this DFS or BFS?

Answer 1

There are not many things to criticize here ... the basic algorithm in general looks good.

The three items I would caution you on are:

1. you are keeping track of the path-count in the paths static variable. This is a pattern that, although works, is not very 'pretty', there's a better way... I'll explain.
2. you modify the source array. This can be OK, but, in general, when you want to modify the source data you should instead work off a copy of the data.
3. all your other variables (the maze itself and the size of the maze) are static.

With a slight shift in the way you think of your search method, instead of updating the number of paths, you should instead think 'how many paths from here?'

Also, lets fix the static variable issues too (we will need two methods for this):

public static final int search(int[][] data) {
    int[] mymap = new int[data.length][];
    for (int i = 0; i < data.length; i++) {
        mymap[i] = Arrays.copyOf(data[i], data[i].length);
    }
    return search(mymap, 0, 0);
}

Now, the search(...) recursive method should return an int, and it takes the maze as input, not from a static variable.

To avoud the use of the 'n' variable, we use the basic information from the maze. The following is a copy/paste of your code with slight modifications:

1. it returns int
2. return-statements inside return a value now
3. the input includes the 'maze' (instead of being a static variable)
4. there are no references to n, just to the a array
5. it has an internal paths variable
6. it changes how it calls exist(...)

public static int search(int[][] a, int i, int j)
{
    if(!exist(i,j) || a[i][j] == 1)
        return 0; // no path here.
    if(i == a.length - 1 && j == a[i].length - 1)
    {
        return 1; // 1 path here.
    }
    a[i][j] = 1; // mark that we have seen this spot here
    int paths = 0; // introduce a counter...
    paths += search(a, i+1,j); // add the additional paths as we find them
    paths += search(a, i-1,j);
    paths += search(a, i,j+1);
    paths += search(a, i,j-1);
    a[i][j] = 0;
    return paths; // return the number of paths available from this point.
}

The exist() function will also need to change:

public static boolean exist(int[][] a, int i, int j)
{
    return i>=0 && j >=0 && i < a.length && j < a[i].length;
}   

Note that this no longer references the n static variable either.

Finally, with these changes (and, really, in the scheme of things they are 'small'), your main method simply becomes:

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[][] a = new int[n][n];
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            a[i][j] = sc.nextInt();
        }
    }
    System.out.println(search(a));

For this, the a does not need to be static either.

If you code the process like I suggest then the methods become much more generic, and you have other advantages like:

1. the methods are all thread-safe now (you can find many paths in parallel using the same methods).
2. the data and the logic are both self-contained.
3. there are no static variables.

Finally, the variable names you have chosen are really short..... consider renaming the a variable at least.

Answer 2

Your recursive search is fine, as long as the paths through the maze are short enough not to overflow the stack. Since you have to find all paths, an exhaustive search is necessary, so I don't think you need to use any fancier algorithms. (Recursion generally results in depth-first search behaviour.)

I agree with @rolfl that static variables should be avoided, and that modifying the input matrix is naughty. However, I recommend a different remedy: make a Maze object. (By the way, class names should be UpperCaseLikeThis in Java.)

Once your Maze object has copied the maze definition into a private instance variable, it's free to do whatever it wants with the array, including modifying it with temporary roadblocks.

I've renamed search() to pathsFrom() to clarify the meaning of its parameters. I've also renamed exist() to isInBounds() for clarity.

The count of the number of paths is not part of the state of the maze, so it should not be an instance variable or a class variable. It should just be returned from the pathsFrom() method.

import java.util.*;

class Maze
{
    private int n;
    private int[][] a;

    /**
     * Array is a square matrix, whose elements are 0 for paths and 1 for walls.
     */
    public Maze(int[][] array)
    {
        // Copy the array, assuming that it is a square matrix
        n = array.length;
        a = new int[n][];
        for (int i = n - 1; i >= 0; i--)
        {
            a[i] = Arrays.copyOf(array[i], n);
        }
    }

    public int pathsFrom(int i, int j)
    {
        if(!isInBounds(i,j) || a[i][j] == 1)
        {
            return 0;
        }
        if(i == n-1 && j == n-1)
        {
            return 1;
        }
        try
        {
            a[i][j] = 1;
            return pathsFrom(i+1,j) +
                   pathsFrom(i-1,j) +
                   pathsFrom(i,j+1) +
                   pathsFrom(i,j-1);
        }
        finally
        {
            // Restore the state of the maze before returning
            a[i][j] = 0;
        }
    }

    private boolean isInBounds(int i, int j)
    {
        return i>=0 && j >=0 && i < n && j < n;
    }

    public static void main(String[] ar)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] a = new int[n][n];
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                a[i][j] = sc.nextInt();
            }
        }
        Maze m = new Maze(a);
        System.out.println(m.pathsFrom(0, 0));
    }

}

In the implementation of pathsFrom() above, I've used a slick language trick to sneak in a statement before returning. That code is equivalent to

        a[i][j] = 1;
        int paths = pathsFrom(i+1,j) +
                    pathsFrom(i-1,j) +
                    pathsFrom(i,j+1) +
                    pathsFrom(i,j-1);
        a[i][j] = 0;
        return paths;

… except that the version using finally restores the state of the matrix even if an exception is thrown.