18. Grid Path Counting with Offline Compute Pods

Problem

DeepMind's evaluation scheduler models a slice of its compute cluster as a grid of pods, each holding one accelerator. A job enters at the top-left pod and must reach the bottom-right pod, and because of how the grid's row and column interconnects hand off work, it can only move one pod to the right or one pod down at each step. Some pods are marked offline and cannot be entered.

Count how many distinct paths the job can take from the top-left pod to the bottom-right pod, moving only right or down, without ever entering an offline pod. If the start or end pod is itself offline, there are zero valid paths.

Source: src/18_grid_path_counting.py

def count_grid_paths(grid: list[list[int]]) -> int:
    ...

Examples:
>>> count_grid_paths([[0, 0, 0], [0, 1, 0], [0, 0, 0]])
2

>>> count_grid_paths([[0, 1], [0, 0]])
1

Step-by-Step Approach

1. Recognize this as a classic grid dynamic-programming problem: the number of ways to reach a cell only depends on the number of ways to reach the cell above it and the cell to its left, since those are the only two cells that can move into it.
2. Handle the obstacle rule first: if the start pod or the end pod is itself offline, short-circuit to 0 immediately — no DP fill can produce a path through a blocked start or end.
3. Initialize a dp table the same shape as the grid, with dp[0][0] = 1 (one way to "reach" the starting pod: already being there).
4. Fill the table row by row, left to right. For every open cell, dp[r][c] = dp[r-1][c] + dp[r][c-1], treating any out-of-bounds neighbor as contributing 0 paths. For every offline cell, force dp[r][c] = 0 regardless of its neighbors.
5. The answer is the value in the bottom-right cell of the completed dp table.
6. Space can be optimized from O(rows·cols) to O(cols) by keeping only the current row, since each cell only ever needs the row directly above it and the cell directly to its left within the same row.

The key insight is that "offline pods block paths" is just another base case in the recurrence, not a separate graph search — folding it directly into the DP transition avoids a second BFS/DFS pass to remove blocked paths after the fact.

Reference solution

def count_grid_paths(grid: list[list[int]]) -> int:
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    if grid[0][0] == 1 or grid[rows - 1][cols - 1] == 1:
        return 0  # start or end pod offline: no path can exist
    dp = [[0] * cols for _ in range(rows)]
    dp[0][0] = 1
    for r in range(rows):
        for c in range(cols):
            if r == 0 and c == 0:
                continue
            if grid[r][c] == 1:
                dp[r][c] = 0  # offline pod: unreachable, contributes no paths onward
                continue
            top = dp[r - 1][c] if r > 0 else 0
            left = dp[r][c - 1] if c > 0 else 0
            dp[r][c] = top + left  # paths in = paths from above + paths from the left
    return dp[rows - 1][cols - 1]

Key Functions & Tricks

• dp[r][c] = dp[r-1][c] + dp[r][c-1] — core recurrence: paths in = paths from above + paths from the left
• Row-major fill order — guarantees dp[r-1][c] and dp[r][c-1] are already computed before dp[r][c] needs them
• Forcing dp[r][c] = 0 on an offline cell — folds the obstacle rule into the same pass instead of a separate filtering step
• Early return on a blocked start/end cell — avoids running the full O(rows·cols) fill when the answer is trivially 0
• Rolling 1D array instead of a full 2D table — reduces space from O(rows·cols) to O(cols) since only the previous row is ever read

How to Recognize This Pattern