Tuesday, 15 September 2015

Count all possible paths from top left to bottom right of a m*n Matrix


A person starts from the uppermost, leftmost corner of a grid. Each cell of grid is 0,1,2,3,4,5,6 or 7. From any cell, he can only go to right cell if this cell is 1, he can only go to lower cell if this cell is 2, he can only go to its diagonally opposite cell if this cell is 3, he can go to right and lower cell if this cell is 4, he can go to right and diagonally opposite cell if this cell is 5, he can go to lower and diagonally opposite cell if this cell is 6, he can go to right and lower and diagonally opposite cell if this cell is 7 and he can not move from this cell if this cell is 0. The following figure shows each of these cases:

Person wants to go to the lowermost, rightmost corner of the grid. You have to find number of paths travelling on which he can reach at destination.

Input :
Input1: An Integer array having  two elements: m, n that depict rows and columns of the grid respectively
Input2: An Integer array containing m*n elements 

Output :
Output will be the number of ways to reach the ending position.

For Example:-
Input1: 4 6
Input2: 1 3 0 0 0 0 0 0 4 5 1 0 0 0 0 6 7 6 0 0 0 0 5 0

Output: 3

Input1: 3 4
Input2: 1 2 0 0 5 0 0 0 7

Output: 1

Note:Press Enter after each input for ex: after entering 4 press enter then enter 6 as scanner nextInt method is used for reading input.

Solution:

import java.util.Scanner;  
 public class MatrixPathProblem {  
      int m, n;  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           // TODO Auto-generated method stub  
           MatrixPathProblem obj = new MatrixPathProblem();  
           int a[] = new int[2];  
           Scanner s = new Scanner(System.in);  
           for (int i = 0; i < a.length; i++) {  
                a[i] = s.nextInt();  
           }  
           obj.m = a[0];  
           obj.n = a[1];  
           int b[] = new int[obj.m * obj.n];  
           for (int i = 0; i < b.length; i++) {  
                b[i] = s.nextInt();  
           }  
           int mat[][] = new int[obj.m][obj.n];  
           int k = 0;  
           for (int i = 0; i < obj.m; i++) {  
                for (int j = 0; j < obj.n; j++) {  
                     mat[i][j] = b[k];  
                     k++;  
                }  
           }  
           System.out.println(obj.path(mat, 0, 0));  
      }  
      private int path(int[][] a, int i, int j) {  
           if (i == m - 1 && j == n - 1)  
                return 1;  
           else if (i == m - 1) {  
                if (a[i][j] == 0)  
                     return 0;  
                else  
                     return 1;  
           } else if (j == n - 1) {  
                if (a[i][j] == 0)  
                     return 0;  
                else  
                     return 1;  
           } else if (a[i][j] == 0)  
                return 0;  
           else if (a[i][j] == 1)  
                return path(a, i, j + 1);  
           else if (a[i][j] == 2)  
                return path(a, i + 1, j);  
           else if (a[i][j] == 3)  
                return path(a, i + 1, j + 1);  
           else if (a[i][j] == 4)  
                return path(a, i + 1, j) + path(a, i, j + 1);  
           else if (a[i][j] == 5)  
                return path(a, i, j + 1) + path(a, i + 1, j + 1);  
           else if (a[i][j] == 6)  
                return path(a, i + 1, j) + path(a, i + 1, j + 1);  
           else if (a[i][j] == 7)  
                return path(a, i, j + 1) + path(a, i + 1, j + 1)  
                          + path(a, i + 1, j);  
           else  
                return 0;  
      }  
 }  

5 comments:

  1. This post is good!

    But it would be much more helpful if it was been explained in brief.

    I have gone through the same interview question which i have placed at http://i.stack.imgur.com/njEoi.png

    But the solution which you have provided has returned wrong results for {2,2} and {1,1,1,1}.
    As, we need to get 0 as output but we are getting the output as 1.

    Explaining the Logic in brief would help to understand!.

    ReplyDelete
  2. Wrong code,
    try input
    1 3 0 0 0 0 0 0 4 5 1 0 0 0 0 6 7 1 0 0 0 0 5 0
    Output should be 0 in this case but still it is 3. Please correct

    ReplyDelete
  3. Sorry for mistake, Output should be 2 acc to my above comment and I have corrected some code. Mail me if you want corrected code.

    ReplyDelete
  4. Wrong code. It assumes that when the person arrives anywhere in the last column, there is a path (except when value is zero). This is plain wrong. The rules still hold in the last column. The person might not be able to move down depending on the content of that cell and any below it. Same goes for last row.

    ReplyDelete