user3840069 - 7 months ago 40

C++ Question

Given a grid of size

`N X N`

`(0,0)`

`(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.

`N=5`

`(2,2)`

`36`

What can be efficient way to count them ?

Answer

you have to know two things :

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.

**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`

Source (Stackoverflow)