Difficulty:

A rabbit is standing at the top-left corner of an

`m X n`

grid (at the`[0, 0]`

cell). There is a carrot at the bottom-right corner (at the`[m - 1, n - 1]`

cell). The rabbit can move to any of these 3 cells in each step if he is not restricted: the adjacent cell to the right, to the bottom, or diagonally to the bottom-right. The rabbit is restricted to the grid boundaries (cannot exit), and he cannot use the cells marked as blocked. Given the size of the grid and a list of blocked cells, calculate how many different ways there are by which he can reach the carrot.For example, on a

`2 X 2`

grid, the rabbit can reach the carrot in 3 different ways:`right->down`

,`down->right`

, and`diagonal`

. If the`[0, 1]`

cell is blocked, there are only 2 ways:`down->right`

and`diagonal`

.The answer will have

`12`

or fewer digits. The top-left and bottom-right cells are not blocked. If there is no way to reach the carrot, simply return`0`

.

carrotWays(3, 3, [ [ 2, 1 ], [ 1, 0 ] ]);

6

- Hint #1