Find Paths Across a Weighted Binary Grid

Problem Statement

You are given an R x C grid of integers where:

• -1 represents a blocked cell (obstacle).
• Any integer w >= 0 represents an open cell with an entry cost of w.

A valid path across the grid must:

1. Start at any open cell in the top row (row = 0).
2. End at any open cell in the bottom row (row = R - 1).
3. Move between 4-directionally adjacent open cells (up, down, left, right).
4. Be a simple path (no cell is visited more than once).

The total cost of a path is the sum of costs of all cells on the path, including the starting cell.

Implement the class GridPathSolver with three methods:

class GridPathSolver:
    def is_reachable(self, grid: list[list[int]]) -> bool:
        """Returns True if there is at least one valid path from row 0 to row R - 1, False otherwise."""
        pass

    def enumerate_paths(self, grid: list[list[int]], max_paths: int) -> list[list[tuple[int, int]]]:
        """Returns up to `max_paths` valid paths, ordered lexicographically by cell coordinates.
        Lexicographical order compares coordinate tuples (r, c) sequentially."""
        pass

    def min_cost_path(self, grid: list[list[int]]) -> tuple[int, list[tuple[int, int]]]:
        """Returns a tuple (cost, path) of the minimum-cost valid path.
        If multiple paths share the minimum cost, return the lexicographically smallest path.
        If no valid path exists, return (-1, [])."""
        pass

Constraints

• 1 <= R, C <= 50
• -1 <= grid[r][c] <= 1000
• 1 <= max_paths <= 100
• R * C <= 500 for enumerate_paths and min_cost_path

Examples

Example 1

grid = [
    [2,  3, -1],
    [-1, 1,  4],
    [ 5, 2,  1]
]
solver = GridPathSolver()

# 1. Reachability
solver.is_reachable(grid) # Returns: True

# 2. Minimum-cost path
solver.min_cost_path(grid)
# Returns: (7, [(0, 1), (1, 1), (2, 1)])
# Cost = 3 + 1 + 2 = 6? Wait: (0, 1)=3, (1, 1)=1, (2, 1)=2 => total = 6.
# Another option: (0, 1)=3, (1, 1)=1, (1, 2)=4, (2, 2)=1 => 9.
# Min cost is 6 with path [(0, 1), (1, 1), (2, 1)].

Example 2 (Single-Row Grid)

grid = [[-1, 4, 2]]
solver = GridPathSolver()
solver.is_reachable(grid) # Returns: True
solver.min_cost_path(grid)
# Returns: (2, [(0, 2)])
# Starting and ending on row 0 (which is also row R-1).

Example 3 (Unreachable Grid)

grid = [
    [ 1, -1],
    [-1,  1]
]
solver = GridPathSolver()
solver.is_reachable(grid) # Returns: False
solver.min_cost_path(grid) # Returns: (-1, [])