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