Finding No. of paths in matrix

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

6 thoughts on “Finding No. of paths in matrix

  1. 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.

  2. 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

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

    }

Leave a comment