Count possible paths through a maze

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 =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?

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

The three items I would caution you on are:

• 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.

• 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.

• 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:

• it returns int

• return-statements inside return a value now

• the input includes the 'maze' (instead of being a static variable)

• there are no references to n, just to the a array

• it has an internal paths variable

• 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:

• the methods are all thread-safe now (you can find many paths in parallel using the same methods).

• the data and the logic are both self-contained.

• there are no static variables.

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

StackExchange Code Review Q#36655, answer score: 4