17. Rabbit and Carrot

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