floor with m rows and n columns: 0 is a free cell, 1 is a cell occupied by a rack. A robot cart starts in the top-left corner (floor[0][0]) and has to reach the loading bay in the bottom-right corner (floor[m - 1][n - 1]).
Each move takes the cart to the neighbouring cell below or to the right, and it can never enter a cell with a rack. If a rack stands on the start or the loading bay, the trip is impossible.
Return the number of distinct routes from the start to the loading bay.
The answer is guaranteed not to exceed 2·10⁹.floor=[[0, 0, 0], [0, 0, 1], [0, 0, 0]] → 3
The rack sits at the right end of the middle row. Without it there would be 6 routes, but three of them pass through the rack's cell, so 3 remain.
floor=[[0, 1], [1, 0]] → 0
Both neighbours of the start are blocked, so the cart cannot move at all.
floor=[[0, 0, 0, 0]] → 1
With a single row there is only one route: keep going right.
m, n ≤ 100floor[i][j] is 0 or 1floor=[[0, 0, 0], [0, 0, 1], [0, 0, 0]]
3
Run checks the first 3 tests in your browser. Submit checks all 105 tests on the server, hidden ones included.