import numpy as np

# Define the directions and the corresponding row and column offsets.
DIRECTIONS = {
    "north": (-1, 0),
    "south": (1, 0),
    "east": (0, 1),
    "west": (0, -1),
}

# Define a function to compute the probability of reaching each cell from each starting cell.
def compute_probabilities(grid, starts, finishes):
    # Initialize the probability matrix with zeros.
    rows, cols = grid.shape
    probs = np.zeros((len(starts), rows, cols))
    # Initialize the optimal command matrix with None.
    commands = np.empty((len(starts), rows, cols), dtype=object)
    commands[:] = None
    # Initialize the queue with the finish cells.
    queue = [(finish, i) for i, finish in enumerate(finishes)]
    # Loop over the queue until it is empty.
    while queue:
        cell, i = queue.pop(0)
        row, col = cell
        # Loop over the possible commands.
        for cmd, (d_row, d_col) in DIRECTIONS.items():
            # Compute the new row and column.
            new_row, new_col = row + d_row, col + d_col
            # Check if the new cell is within the grid.
            if new_row >= 0 and new_row < rows and new_col >= 0 and new_col < cols:
                # Check if the new cell is not a wall.
                if grid[new_row, new_col] != "wall":
                    # Compute the probability of reaching the new cell from the current cell.
                    if cmd in ("north", "south"):
                        prob = 0.5 * probs[i, new_row, new_col] + 0.5 * probs[i, row, col]
                    else:
                        prob = 0.5 * probs[i, new_row, new_col] + 0.5 * probs[i, row, col]
                    # Update the probability and command matrices if the new probability is higher.
                    if prob > probs[i, new_row, new_col]:
                        probs[i, new_row, new_col] = prob
                        commands[i, new_row, new_col] = cmd
                        # Add the new cell to the queue if it hasn't been visited yet.
                        if (new_row, new_col) not in [c[0] for c in queue]:
                            queue.append(((new_row, new_col), i))
    return probs, commands

# Define a function to check whether a pair of interesting start and finish cells is drivable.
def is_drivable(grid, start, finish):
    # Compute the probability of reaching the finish cell from the start cell.
    probs, commands = compute_probabilities(grid, [start], [finish])
    prob = probs[0, finish[0], finish[1]]
    # Return True if the probability is at least 1−