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