Find total number of paths in a matrix of 0's and 1's

Question

I am working on a program which states that:

You are given a 2-D matrix with M rows and N columns.You are initially positioned at (0,0) which is the top-left cell in the array. You are allowed to move either right or downwards. The array is filled with 1’s and 0’s. A 1 indicates that you can move through that cell, a 0 indicates that you cannot move through that cell. Return the number of paths from top-left cell to bottom-right cell.(i.e. (0,0)to(M-1,N-1)). Since answer can be large thus you have to return ans%(10^9+7).

I tried to implement it and it is working for some scenarios but fails for some cases:

static int count(int a[][], int i, int j) {
    int rows = a.length;
    int cols = a[0].length;
    if(a[i][j] == 0)  return 0;
    if (i == rows - 1 && j == cols - 1)
        return a[i][j];
    else if (i == rows - 1)
        return a[i][j + 1];
    else if (j == cols - 1)
        return a[i + 1][j];
    else if (a[i][j] == 1)
        return count(a, i + 1, j) + count(a, i, j + 1);
    else
        return 0;
}

It fails for below array: {{1,1}, {0,1}}

Can you please help me what is the issue in this program?

Update:

Thanks @Johnny Mopp, it solved the above test case. How can we improve the performance of this program?

I think you need to check the value of the cell first thing. Ex: `if (a[i][j] == 0) return 0;` — 001, Feb 27 '18 at 21:51
"It doesn't work" doesn't help us. What does the program do as it fails, and how does it differ from the expected behavior? — Brandon McKenzie, Feb 27 '18 at 21:53
I agree with Johnny Mopp. If you are in a cell that has value 0 and is on the border, your code right now will proceed on that border instead of returning 0. How about creating a matrix that stores for which cell there are which amounts of ways from it and then print it as control? — Aziuth, Feb 27 '18 at 21:53
This kind of issue is best approached using a debugger (see here: https://stackoverflow.com/q/25385173). — korolar, Feb 27 '18 at 21:56
@JohnnyMopp, Thank you, it worked now, is there a way to improve the performance of this program? — learner, Feb 27 '18 at 21:57

bebidek · Accepted Answer · 2018-02-27T22:54:48.007

5

First if should check value of a[i][j]. It it's 0, you should return 0.

And about performance, algorithm written this way is very slow, as you calculate the same value many times. Use memorisation (create second array and save every value you return and at the beginning of function check first if you haven't calculated it before) or solve it with dynamic programming.

EDIT: You forgot about your modulo 10^9+7.

SECOND EDIT (responding to your comment): It would be something like that. I divided it to three loops so that main (third) loop has less operations to do and function is quite faster for big data. I also changed direction of computing but it's not important at all.

static int count_dp(int a[][]){
    int rows = a.length;
    int cols = a[0].length;
    int[][] dp = new int[rows][cols];

    dp[0][0] = a[0][0];

    for(int i=1;i<rows;i++)
        if(dp[i-1][0]==1 && a[i][0]==1)
            dp[i][0] = 1;

    for(int i=1;i<cols;i++)
        if(dp[0][i-1]==1 && a[0][i]==1)
            dp[0][i] = 1;

    for(int i=1;i<rows;i++)
        for(int j=1;j<cols;j++)
            if(a[i][j]==1)
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%1000000007;

    return dp[rows-1][cols-1];
}

edited Feb 27 '18 at 22:54

answered Feb 27 '18 at 21:58

bebidek

592
3
8

Can you give me a snippet how to do this with dynamic programming? – learner Feb 27 '18 at 22:19
Something similar to your algorithm, but you don't use recursion. Create second array of the same size. Then you just loop through the array in correct order (for example `for(int i=rows-1;i>=0;i--) for(int j=cols-1;j>=0;j--)`) and calculate values as you do now, but instead of recursion you just take previously computed values from array. – bebidek Feb 27 '18 at 22:28
I tried the approach, but not able to get an answer, can you please provide a solution using dynamic programming – learner Feb 27 '18 at 22:35
Nice answer, I have upvoted. I had a DP solution much earlier which starts bottom right and goes to top left and answer is dp[0][0]. I am very interested in your optimizations. My i,j loop has 4 if statements and can now see how you got rid of three of them (bottom/right cell, and each outer row/col) leaving just one if statement. Very nice... – Ian Mc Feb 27 '18 at 23:19

score 0 · Answer 2 · answered Aug 23 '20 at 01:29

def path_finder(i,j,m,l,n):
    if i==n-1 and j==n-1:
        if m[i][j]==1:
            l.append([i,j])
            return 1
        else:
            return 0
    if i==n or j==n:
        return 0
    if m[i][j]==0:
        return 0
    l.append([i,j])
    fl=path_finder(i+1,j,m,l,n)   #vertical movement 
    fr=path_finder(i,j+1,m,l,n)   #horizontal movement 
    if not (fl or fr):
        l.pop()
        return 0
    return 1

if __name__=='__main__':
    n=4   #size od matrix
    i=0
    j=0
    m=[[1,1,1,0],
       [1,0,1,1],
       [1,1,0,1],
       [1,1,0,1]]
    l=[]  #empty list to store path indices
    found=path_finder(i,j,m,l,n)
    if found==1:
        for i in l:
            print('({0},{1})'.format(*i),end=' ')
    else:
        print(-1)
# A recursive approach to the solution.
# Works for all values of n if we can move only right and 
down. Fails if we have to move up or left,Eg: for matrix 
shown below we have to move up in order to get to n, n
[[1 1 1 1 1], 
 [1 0 0 0 0], 
 [1 0 1 1 1], 
 [1 0 1 0 1], 
 [1 1 1 0 1]]

score 0 · Answer 3 · answered May 21 '23 at 12:17

A little late to the party, but this problem can be easily solved using Dynamic Programming as follows -

static int mat[][] = new int[m][n]; //for e.g. m=3, n=3

public static int countPathUsingDp(int m, int n) {
    for(int i=0;i<m;i++)
        mat[i][0] = 1;

    for(int j=0;j<n;j++)
        mat[0][j] = 1;

    for(int i=1;i<m;i++)
        for(int j=1;j<n;j++)
            mat[i][j] = mat[i-1][j] + mat[i][j-1];

    return mat[m-1][n-1];
}

The time complexity: O(m*n)

Solution: You assign path to base[0,0] from every element, as you traverse.

Find total number of paths in a matrix of 0's and 1's

3 Answers3