1

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.

Guy Avraham
  • 3,482
  • 3
  • 38
  • 50
  • There are an infinite amount if the path can loop. Otherwise, what's your attempt at solving this? – Nelfeal Oct 31 '18 at 17:09
  • @Nelfeal Paths don't loop: https://en.wikipedia.org/wiki/Path_(graph_theory) – Ari Oct 31 '18 at 17:14
  • Are we only moving down and to the right, or are moves up and to the left valid? If the latter then my solution needs adjusting. – Dave Oct 31 '18 at 17:18

5 Answers5

1

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));
}
Guy Avraham
  • 3,482
  • 3
  • 38
  • 50
  • You are assuming that the valid moves are (0,1) and (1,0). That isn't stated in the problem. – stark Oct 31 '18 at 17:17
1

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.

Guy Avraham
  • 3,482
  • 3
  • 38
  • 50
Dave
  • 7,460
  • 3
  • 26
  • 39
0

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

nightfury1204
  • 4,364
  • 19
  • 22
0

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.

Ari
  • 7,251
  • 11
  • 40
  • 70
0

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)
SomeDude
  • 13,876
  • 5
  • 21
  • 44