Number of paths in 2D matrixPuzzle: Given a 2D matrix with N rows and M columns. You have to move from upper left corner to diagonally opposite, lower right corner. If only valid moves at any given cell are Move 1 cell Right or Move 1 cell down, then calculate the total number of ways in which you can move from source to destination. ![]() Solution: In any path, total moves required to move from start to end are N+M-2 Out of these, (N-1) moves must be down and (M-1) moves must be towards right. (N-1) moves can be chosen from (N+M-2) moves in N+M-2CN-1 ways. So total number of ways to move are also the same = N+M-2CN-1 = (N+M-2)! / (N-1)! (M-1)! Verification: For 3x2 matrix, ways = 3!/2!1! = 3 For 3x3 matrix, ways = 4!/2!2! = 6 |
Got a thought to share or found a
bug in the code?
We'd love to hear from you:
Name: | |
Email: | (Your email is not shared with anybody) |
Comment: |
Facebook comments: