user3840069 user3840069 - 1 year ago 57
C++ Question

Count paths in a grid with multiple checkpoints

Given a grid of size

. Its bottom-left point is
and top-right element is

We can traverse the grid in either top or right direction. We have to find the number of ways to traverse from the bottom-left to top-right point. There are some checkpoints which we have to visit in every path. There is at least one valid path.

Example : Let
and we have 1 checkpoint at
then here answer is

Note : I need to count only valid paths and have no concern in finding them.

What can be efficient way to count them ?

Answer Source

you have to know two things :

  1. Rule of product: it means that number of ways from start to end is equal number of ways from start to middle point * number of ways from middle point to end.

  2. C(R,R+U) ( R is number of your right moves and U is the number of up moves it means if you want to go from (a,b) to (c,d) then R = c-a and U = d-b, and C(R,R+U) = (R+U)!/R!U! ) is the answer of how many ways there are from bottom left to top right in a grid.

Example in your example from my second rule we have :

number of moves from (0,0) to (2,2) because after two right move from 0 you reach 2 and after two up move from 0 you reach 2 so R=2 and U=2 so C(2,2+2) = C(2,4) = 4!/2!2! = 6. And doing the same for R and U number of moves from (2,2) to (4,4) is C(2,2+2) = C(2,4) = 4!/2!2! = 6

and from the first rule we have number of all possible moves : 6 * 6 = 36