user3840069 - 10 days ago 6
C++ Question

Count paths in a grid with multiple checkpoints

Given a grid of size

`N X N`
. Its bottom-left point is
`(0,0)`
and top-right element is
`(N-1,N-1)`
.

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
`N=5`
and we have 1 checkpoint at
`(2,2)`
`36`
.

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

What can be efficient way to count them ?

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`