[Math] Number of paths in a MxN matrix

combinationscombinatoricsgraph theory

Given a MxN grid, how many paths can there be to reach the bottom right cell from the top left cell?
The only constraints are one cannot visit a cell more than once, I tried checking the other solutions but they only consider right and down moves whereas this one can have left and up moves too. Any help is appreciated 🙂

For example, consider a 3×3 matrix,
I converted into a graph as shown below:

enter image description here

where the numbers associated with node represent cell number counting from top left to bottom right, then the number of paths would be 12 as shown below:
{
{1, 2, 3, 6, 5, 4, 7, 8, 9}, {1, 2, 3, 6, 5, 8, 9}, {1, 2, 3, 6, 9},
{1, 2, 5, 4, 7, 8, 9}, {1, 2, 5, 6, 9}, {1, 2, 5, 8, 9},
{1, 4, 5, 2, 3, 6, 9}, {1, 4, 5, 6, 9}, {1, 4, 5, 8, 9},
{1, 4, 7, 8, 5, 2, 3,6, 9}, {1, 4, 7, 8, 5, 6, 9}, {1, 4, 7, 8, 9}
}

The above paths are shown below:

enter image description here

Even though I show each and every path here, I don't need them , I just need the count stating number of paths possible

Best Answer

If m==n you can find the no of paths to reach the bottom right cell from the top left cell using slight modification of Backtracking problem. Find below the code in Java.

public class Robot {
    private static int count = 0;
    public static void main(String[] args) {
        Robot robot = new Robot();
        int m = 5, n = 5;
        boolean Visited[][] = new boolean[5][5];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++)
                Visited[i][j] = false;
        }
        robot.traverse(Visited, 0, 0, m, n);
        System.out.println(count);
    }
    /**
     * 
     * @param Visited array
     * @param index i
     * @param index j
     * @param max Row m
     * @param max column n
     */
    private void traverse(boolean Visited[][], int i, int j, int m, int n){
        if(i==m-1&&j==n-1){
            count++;
            return;
        }
        if(isSafe(i, j, m, n, Visited)){
            Visited[i][j]=true;
            traverse(Visited, i, j+1, m, n);
            traverse(Visited, i+1, j, m, n);
            traverse(Visited, i-1, j, m, n);
            traverse(Visited, i, j-1, m, n);
            Visited[i][j] = false;
        }
    }
    /**
     * 
     * @param index i
     * @param index j
     * @param max Row m
     * @param max Column n
     * @param Visited array
     * @return isSafe or not
     */
    private boolean isSafe(int i, int j, int m, int n, boolean Visited[][]){
        if(i>=0&&j>=0&&i<m&&j<n&&!Visited[i][j])
            return true;
        else
            return false;
    }

}
Related Question