def make_grid_neighbors(grid: List[List[int]]):
    """grid[r][c] == 1 means blocked. Returns a neighbors_fn."""
    rows, cols = len(grid), len(grid[0])

    def neighbors(state):
        r, c = state
        result = []
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                result.append(((nr, nc), 1.0))
        return result

    return neighbors


def manhattan(a: State, b: State) -> float:
    return abs(a[0] - b[0]) + abs(a[1] - b[1])


if __name__ == "__main__":
    grid = [
        [0, 0, 0, 0, 0],
        [0, 1, 1, 1, 0],
        [0, 0, 0, 1, 0],
        [1, 1, 0, 1, 0],
        [0, 0, 0, 0, 0],
    ]
    start, goal = (0, 0), (4, 4)
    result = astar(start, goal, make_grid_neighbors(grid), manhattan)
    if result:
        path, cost = result
        print(f"Path found, cost={cost}:")
        for step in path:
            print(step)
    else:
        print("No path exists.")
