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

Thanks.

ReplyDeleteThis post is good!

ReplyDeleteBut 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!.

Wrong code,

ReplyDeletetry 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

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.

ReplyDeleteWrong 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