CODEWITHSUNDEEP
algorithm
approximatehack
approximatehack

Reputation: 171

Number of monotonic paths in a rectangular grid avoiding certain points

In a rectangular grid of size m*n, the number of paths from (0,0) to (m,n) (without backtracking) is (m+n)!/(m!*n!). Now if there are certain points in the grid which we want to avoid, how can we calculate the number of paths avoiding those points?

Upvotes: 2

Views: 2645

Answers (3)

Jon Noel
Jon Noel

Reputation: 101

A natural question here is to ask: for any given k, what is the maximum number of monotonic paths avoiding a set S of k points (where the maximum is over all possible sets S)?

This is actually an open problem raised in a paper of Johnson, Leader and Russell: http://arxiv.org/pdf/1309.4643.pdf

Upvotes: 0

Rafał Dowgird
Rafał Dowgird

Reputation: 45071

The (recursive) equations defining the solution are as follows:

  • number of monotonic paths from (m,n) to (m,n) is 1
  • number of monotonic paths from any forbidden point to (m,n) is 0, same for points with first coordinate greater than m or second greater than n.
  • number of monotonic paths from any other point (x,y) to (m,n) is the sum of:
    • number of paths from (x+1,y) to (m,n) and
    • number of paths from (x,y+1) to (m,n) (see above for dealing with the increment moving us out-of-grid)

Obviously, as Qnan stated, you need to use dynamic programming (i.e. memorize partial solutions to avoid exponential time) to solve these for (0,0).

Upvotes: 2

Qnan
Qnan

Reputation: 3744

I don't think there's a reasonable analytical solution for a grid with exactly k points blocked, but one can count the paths using a dynamic programming algorithm.

An analytical solution is troublesome because the number of blocked paths will depend no only on the number of blocked nodes and position of each node, but also on their relative positions. E.g. in a 4x4 grid, these two configurations give very different results:

....      ....
..x.      .xx.
.x..      ....
....      ....

It is easy to see that the former allows for only two monotonic paths, while the latter has at least 5.

Upvotes: 1

Related Questions