obstacleGrid is a map with m rows and n columns. A 0 is an open cell and a 1 is a rock. A token starts in the top-left cell and has to reach the bottom-right cell, moving one cell right or one cell down at a time. It can never step onto a rock.
Return the number of different routes the token can take from start to finish. If a rock sits on the start or the finish, or the rocks cut every route, the answer is 0.
The rock next to E means every route enters the finish from above, and the rock in the second row blocks every route that turns down early. Only RRRDD and RRDRD are left.
The only way round the two rocks is down the left edge and along the bottom: DDRR.
Both cells next to the start are rocks, so the token cannot move at all.
Constraints
m == obstacleGrid.lengthn == obstacleGrid[i].length1 <= m, n <= 100obstacleGrid[i][j] is 0 or 1.2 × 10⁹ ways. So the answer, and every count along the way, fits in a 32-bit signed integer.A route into any cell arrives either from the cell above or from the cell to its left, so the number of routes to an open cell is the sum of those two counts. A rock has no routes at all.
2