Number of paths in a MxN matrix 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 3x3 matrix,
I converted into a graph as shown below:

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:

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

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;
    }

}

