Problem : Given a matrix of size m*n of 1’s and 0’s find the Number of paths from matrix[0][0] to matrix[m-1][n-1], using the following moves :
if a[i][j] == 1 , you can move right and downwards.
if a[i][j] == 0 , move not allowed.
For ex :
1 1 1 1
1 1 1 1
1 0 1 1
1 1 1 1
No of paths = 11
Solution :
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class NoOfPathsInMatrix { int m,n; int arr[][]=null; public static void main(String[] args)throws IOException { NoOfPathsInMatrix obj=new NoOfPathsInMatrix(); BufferedReader br =new BufferedReader(new InputStreamReader((System.in))); System.out.println("Enter the no of rows in matrix : "); obj.m = Integer.parseInt(br.readLine()); System.out.println("Enter the no of cols in matrix : "); obj.n = Integer.parseInt(br.readLine()); obj.arr = new int[obj.m][obj.n]; for(int i=0; i< obj.m;i++) { System.out.println("Enter "+(i+1)+"th row : "); for(int j=0;j<obj.n;j++) { String s = br.readLine(); obj.arr[i][j] = Integer.parseInt(s); } } System.out.println("No of paths : "+obj.noOfPaths(obj.arr,0,0)); } int noOfPaths(int a[][], int i,int j) { if(i==m-1 && j==n-1) return a[i][j]; else if (i==m-1) return a[i][j+1]; else if (j==n-1) return a[i+1][j]; else if(a[i][j]==1) return noOfPaths(a,i+1,j) + noOfPaths(a,i,j+1); else return 0; } }
What does this part of code do ?
else if (i==m-1)
return a[i][j+1];
else if (j==n-1)
return a[i+1][j];
If i == m-1 then we are in the last row.
Elements of last row can be reached by above cell or left cell.
Bur here we are just returning the values of the next cell. Same for the last column.
Why so ?
If you are a cell a[i][j], then No. of paths from this cell to a[m-1][n-1] = No. of paths from a[i+1][j] + No. of paths from a[i][j+1].
Initially a[i][j] = 1, which mean cell is reachable.
or a[i][j] = 0, which means cell is not reachable.
We recursively add these values(i.e. 1’s ) to get the no. of paths.
does not work, it just returns 0 which is the latest else block
Let’s say it’s a 1d array: 1 1 1 1 0 1
then there is no path existed.
But according the function it returns 1
That code is wrong. The right way:
static int numberOfPaths(int [][]a, int M, int N) {
int m = a.length;
int n = a[0].length;
if(M == m-1 && N == n-1 || a[M][N] == 0)
return a[M][N];
else if (M == m-1)
return numberOfPaths(a, M, N + 1);
else if (N == n-1)
return numberOfPaths(a, M + 1, N);
else if(a[M][N] == 1)
return numberOfPaths(a, M+1, N) + numberOfPaths(a, M, N + 1);
else
return 0;
}
Thanks for your solution.It helped me to solve one similar question which is asked in one interview.
Here is the question http://techno-terminal.blogspot.in/2015/09/count-all-possible-paths-from-top-left.html