4
$\begingroup$

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:

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

$\endgroup$
  • $\begingroup$ Did you try setting up a recursive relation ? $\endgroup$ – Shailesh Sep 5 '15 at 4:39
  • $\begingroup$ unfortunately,I'm not so good at math, that's why i'm seeking help of you guys :) $\endgroup$ – Pruthvi Raj Sep 5 '15 at 4:44
  • $\begingroup$ The title question asks about an $M\times N$ matrix. You present a $3 times 3$ example, but why do you add the $2,4$-edge? $\endgroup$ – Leen Droogendijk Sep 5 '15 at 5:53
  • $\begingroup$ I present 3x3 as it was simple for me to explain, thank you corrected the question, the (2,4) edge shouldn't have been there :) $\endgroup$ – Pruthvi Raj Sep 5 '15 at 6:02
1
$\begingroup$

For the case $M=N$ this is OEIS A$007764$; no closed form, recurrence, or generating function is given. There is a link to this paper, which has information on asymptotics for this and related problems; I have not looked at it in any detail, however. Finally, there is an OEIS Wiki stub that gives the figures for $N\le M\le 6$ and shows question marks for other values unless $M=N$ or $N\le 2$.

$\endgroup$
  • $\begingroup$ @PruthviRaj: You're welcome! $\endgroup$ – Brian M. Scott Sep 6 '15 at 2:24
2
$\begingroup$

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

}
$\endgroup$
  • $\begingroup$ it is even possible to do this for m != n case too but i was looking for any recurrence relation or generating function that can sum up to it, thanks for posting the code though :) $\endgroup$ – Pruthvi Raj Oct 20 '15 at 9:08
  • $\begingroup$ Yeah it will work in that m!=n case also. $\endgroup$ – Aditya Anand Krishna Oct 20 '15 at 9:26
0
$\begingroup$

As @Shailesh mentioned in the comments, you can do this with a recurrence relation. Suppose you have reached the bottom left corner by some series of steps. Now, go back one step: you are now either at the node above the corner, or beside it. If we write the number of ways to reach the corner node of an $m \times n$ grid as $a_{m,n}$, then we can write $$a_{m,n} = a_{m,n-1} + a_{m-1,n}$$ because you must first reach the penultimate node, and then take the final step. Note that $a_{m,n} = a_{n,m}$ because we are essentially counting the same thing. The initial values for this recurrence are $a_{1,1} = 1$, $a_{m,0} = a_{0,m} = 0$.

An interesting fact, however, arises now. If you write the values of $a_{m,n}$ in a grid, you will see that every number is the sum of the number above it and the number beside it... and the first row and column are both filled with 1s! This is nothing but (try to find this yourself first)

Pascal's triangle, and the numbers are binomial coefficients.

$\endgroup$
  • 1
    $\begingroup$ No, this would be the solution when only one horizontal direction and one vertical direction is allowed. That's a different problem. $\endgroup$ – Leen Droogendijk Sep 5 '15 at 9:04
  • $\begingroup$ I've already found this on the internet in other question this worked only when the moves were restricted to right and down $\endgroup$ – Pruthvi Raj Sep 6 '15 at 6:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.