Grid Paths With Blocks
Problem
A robot starts in the top-left cell of a grid and wants to reach the bottom-right cell, moving only right or down. Cells marked 1 are blocked and cannot be entered, while cells marked 0 are free. Count the distinct paths the robot can take, which is 0 when the start, the finish, or every route between them is blocked.
Examples
Input: [[0, 0, 0],
[0, 1, 0],
[0, 0, 0]]
Output: 2
Why: the blocked centre leaves one route along each edgeInput: [[0, 1],
[1, 0]]
Output: 0
Why: both routes out of the start are blockedInput: [[0]]
Output: 1
Why: edge case, the robot already stands on the finishHints
0 / 3
The number of ways to stand on a cell is decided entirely by the cells the robot could have arrived from, which are the one above and the one to the left.
Fill the grid row by row so that both contributing cells are already known when you compute a cell, and let a blocked cell contribute nothing at all.
Seed the start with a single way, then sweep each row left to right. Set a blocked cell to zero ways, and otherwise add the ways from the cell to its left to the ways already recorded from the row above. Reusing one row of counters is enough, because the value sitting in a slot before you overwrite it is the count from the row above.
Solution
Paths into a cell equal paths into the cell above plus paths into the cell to the left, and a blocked cell simply has zero. Sweeping row by row means a single row of counters can be reused: before a slot is overwritten it still holds the count from the row above, and the neighbour to the left has already been updated for the current row. The start is seeded with one way, and a blocked start short-circuits to zero. Time is O(rows times cols), and space is O(cols).
def paths_with_blocks(grid):
if not grid or grid[0][0] == 1: return 0 # a blocked entrance ends it
rows, cols = len(grid), len(grid[0])
ways = [0] * cols # one row of counters, reused downward
ways[0] = 1 # a single way to stand on the start
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
ways[c] = 0 # nothing can pass through a blocked cell
elif c > 0:
# the slot still holds the row above, add the cell to the left
ways[c] += ways[c - 1]
return ways[-1]
print(paths_with_blocks([[0, 0, 0], [0, 1, 0], [0, 0, 0]])) # -> 2
print(paths_with_blocks([[0, 1], [1, 0]])) # -> 0
print(paths_with_blocks([[0]])) # -> 1Stuck on the idea rather than the code? DP on Grids covers it.