CODEWITHSUNDEEP
arraysalgorithm
Guy Avraham
Guy Avraham

Reputation: 3690

Calculate the number of paths in a two dimensional array from arr[0,0] to arr[N,M] where you can move only right and down

Given a two dimensional array with size of [N,M] calculate the number of different valid paths (where you do not exit from the "array bounds" throughout the path) from the "top left" (arr[0, 0]) to the "bottom right" (arr[N - 1, M - 1]) of the array.

Upvotes: 1

Views: 755

Answers (5)

Dave
Dave

Reputation: 9075

Think of it this way. You have a certain number of 'move right' moves and a certain number of 'move down' moves, and any ordering of these is valid and unique.

This is (N+M)! / (N! * M!)

i.e., the number of permutations of the moves, divided by the number of times we're multi-counting both types of move.

Upvotes: 1

Ari
Ari

Reputation: 7556

Converting the matrix to a graph, this is a classic backtracking problem:

Backtracking: Start from the top left corner:

  • You have these move candidates: move right, down, left, and up

  • Consider all moves that are valid as an option. A move is valid when:

    1. You don't exit the boundary of the matrix
    2. You don't visit a node that was previously visited on the path from root to the current node

Repeat the above for each valid option recursively.

Every time that you hit the right corner, you return 1 to the higher level.

Here is a reference to a similar problem.

Special Case: DAG

Notice that if we only allow right and down moves, the equivalent graph will be a DAG, for which there are more efficient solutions here and here.

Upvotes: 0

SomeDude
SomeDude

Reputation: 14228

Consider a point (i, j) it could be reached from either top or left.

Top means the above row, so the point was (i-1,j).

Left means the left column, so the point was (i, j-1).

The basic expression is f(i,j) = f(i-1,j) + f(i,j-1) You could use this write a program that uses dynamic programming.

dp[i][j] = dp[i-1][j] + dp[i][j-1]

base cases would be 

when you go along the columns in the first row:
for all j = 1 to number of columns
dp[0][j] = 1 // there is one path along that row for any (0,j)

similarly when you go down along the rows in the first column.
for all i = 1 to number of rows
dp[i][0] = 1 // there is one path along that column for any (i,0)

Upvotes: 0

nightfury1204
nightfury1204

Reputation: 4654

For arr[0,0] to arr[n-1,m-1], number of paths: (n-1+m-1)C(n-1) or (n-1+m-1)C(m-1)

enter image description here

Or

enter image description here

Upvotes: 0

Guy Avraham
Guy Avraham

Reputation: 3690

We will use a recursive solution, where:

1) The stop condition will return:

  • 1, if we reached the arr[N,M].

  • 0, if we went out of "bounds" of the array.

2) The recursive call will invoke the function again, once where we move right and once where we move down.

NOTE: dim1 & dim2 are always sent with the original size of the array (N,M).

The implementation of the recursive function will be:

int numOfPathsToEndOfTwoDimMatrix(int x, int y, int dim1, int dim2)
{
    if (x == dim1 - 1 && y == dim2 - 1)
    {
        return 1;
    }

    if (x > dim1 - 1 || y > dim2 - 1)
    {
        return 0;
    }

    return numOfPathsToEndOfTwoDimMatrix(x + 1, y, dim1, dim2) + numOfPathsToEndOfTwoDimMatrix(x, y + 1, dim1, dim2);
}

And the invocation of the function will be as follows:

void main(int argc, char** argv)
{
    int n = 3;
    int m = 3;
    printf("numOfPathsToEndOfTwoDimMatrix(0,0, %d, %d) returned:%d \n", n, m, 
    numOfPathsToEndOfTwoDimMatrix(0,0, n, m));
}

Upvotes: 1

Related Questions