CODEWITHSUNDEEP
carrays
Yan4321
Yan4321

Reputation: 339

Find number of paths in a 2d binary array (C)

I have been asked this question during an interview, and have been struggling to find an elegant solution (in C), Problem statement:

Write a function in C ‘numberOfPaths’ which takes in the above two dimensional array, return the number of valid paths from the top-left cell to the bottom-right cell (i.e. [0,0] to [M-1,N-1]).

Edit: forgot to mention that the requirement is for a recursive solution

help would be greatly appreciated! Thanks

Upvotes: 0

Views: 3326

Answers (5)

Sreejith Menon
Sreejith Menon

Reputation: 1087

This is a python solution, I have put explanations in the comments. 

def find_num_paths(arr_2D, i, j):
# i,j is the start point and you have to travel all the way back to 0,0
    if i == j and i == 0:
        return 1 # you have reached the start point

    if i < 0 or j < 0 or arr_2D[i][j] == 0: # out of range or no path from that point
        return 0

    if arr_2D[i][j] == 1:
        return find_num_paths(arr_2D, i, j-1) + find_num_paths(arr_2D, i-1, j) + find_num_paths(arr_2D, i-1, j-1) # you could go one step above, to the left or diagonally up.

Upvotes: 0

arccoder
arccoder

Reputation: 57

Try this function its a preliminary step before printing all the paths. If the size of the vector Out is 0 then the # of paths are 0, but if size(Out) > 0 then the size of vector Nodes + 1 are the total number of paths from top left to bottom right.

#include <iostream>
#include <vector>

using namespace std;

typedef vector<pair<int,int> > vPii;

bool pathTL2BR( int Arr2D[][4], vPii &Out, vPii &Nodes, 
                int _x,int _y, int _M, int _N)
{
    bool out1 = false;
    bool out2 = false;
    if( Arr2D[_x][_y] == 1 )
    {
        if( _y+1 < _N )
            out1 = pathTL2BR( Arr2D, Out, Nodes, _x, _y+1, _M, _N);

        if( _x+1 < _M )
            out2 = pathTL2BR( Arr2D, Out, Nodes, _x+1, _y, _M, _N);

        if( (out1 || out2) ||
            ( (_x == (_M-1)) && (_y == (_N-1)) ) )
        {
            if(out1 && out2)
                Nodes.push_back( make_pair(_x,_y ) );
            Out.push_back( make_pair(_x,_y ) );
            return true;
        }
        else
            return false;
    }
    else
        return false;
}

// Driver program to test above function
int main()
{
    int Arr2D[][4] = {
                    {1,1,1,1},
                    {0,1,0,1},
                    {0,1,0,1},
                    {0,1,0,1}
                    };

    vPii Out;
    vPii Nodes;
    vector<vPii> Output;
    pathTL2BR( Arr2D, Out, Nodes, 0, 0, 4, 4);

    return 0;
}

Upvotes: 0

user3920832
user3920832

Reputation: 1

#include <stdio.h>

int count=0;
int maxrows = 10;
int maxcols = 10;
int M, N;

void DFS (int array[][10], int x, int y)
{
int r, c;

/* process element at input row and column */

if (array [x][y]==0 || x>M || y>N){
/* no path forward; return */
    return;
}
if (x==M-1 && y==N-1){
    /* found path; increment count */
    count++;
    return;
}
/* recurse: to matrix starting from same row, next column */
r = x;
c = y +1;
if (c < N-1) {
    DFS (array, r,c);
} else {
    /* if last column - check to see  */
    /* if rest of rows in last column allow for a path */
    int tr = r;
    while ( tr <= M-1)  {
        if (array[tr][c] == 1) {
            tr++;
        }       
        else {
            return;
        }
    }
    /* reached last node - path exists! */
    count++;
}
/* recurse: to matrix starting from next row, same column */
r = x+1;
c = y;
if (r < M-1) {
    DFS (array, r,c);
} else {
    /* if last row - check to see  */
    /* if rest of columns in last row allow for a path */
    int tc = c;
    while ( tc <= N-1)  {
        if (array[r][tc] == 1) {
            tc++;
        } else {
            return;
        }
    }
    /* reached last node - path exists! */
    count++;
}
}

int main () {
int i, j;
    scanf("%d %d",&M,&N);
    int a[10][10] = {};
int row, col;

    for(i=0;i<M;i++)
            for(j=0;j<N;j++)
                    scanf("%d", &a[i][j]);
    if ((M > maxrows) || (N > maxcols)) {
    printf("max of 10 rows and 10 cols allowed for input\n");
        return (-1);
    };
/* print input matrix */
    for(row=0;row<M;row++) {
            for(col=0;col<N;col++){
                    printf("%d ",a[row][col]);
            }
            printf(" EOR\n");
    }
DFS(a,0,0);
    printf("number of paths is %d\n", count);
    return 0;
}

Upvotes: 0

coder hacker
coder hacker

Reputation: 4868

If you are looking for a recursive solution you can use DFS.

DFS (array, x, y)
{
if (array [x][y]==0 || x>M || y>N){
    return;
}
if (x==M && y==N){
    count++;
    return;
}
DFS (array, x, y+1);
DFS (array, x+1, y);
}

Upvotes: 1

happydave
happydave

Reputation: 7187

The number of paths to a given point is just the number of paths to the point above, plus the number of paths to the point to the left. So, the pseudo-code would roughly be:

num_paths[0][0] = 1;
for (x = 0; x < M; ++x)
   for (y = 0; y < N; ++y)
      if (!allowed_through[x][y])
         num_paths[x][y] = 0;
      else
         num_paths[x][y] = num_paths[x-1][y] + num_paths[x][y-1];

You need special cases for x=0 and y=0, but otherwise, I think that should do.

Upvotes: 0

Related Questions