BFS with extra state: keys and wall breaks

The shortest path in a grid when you may break through up to k obstacles is a BFS whose nodes carry more than the cell. Two visits to the same cell differ in how many breaks are still allowed, so the node becomes (row, column, breaks left), and the first time the search reaches the target in any such state is the fewest steps. The same idea covers doors that need keys, fuel that runs out and anything else that changes which moves are allowed. The work is in choosing that extra state and counting the states before you code.

The problem: a robot that may drill through rock

1. On the 6 × 7 mine in the diagram, the robot needs 17 steps with k = 0, 13 with k = 1 and 11 with k = 2.
2. ["..##", "##..", "...."] with k = 0 gives −1: the start is walled in. With k = 1 it gives 5.
3. A 40 × 40 block of rock, open only at the two corners, gives 78 steps once k is at least 77.

The brute force: try every set of drilled cells

Choose which rock cells to drill, open them, and run a plain BFS; try every set of at most k cells and keep the best answer. It is correct, and on the mine it is quick, because the mine has only 16 rock cells:

"""Fewest steps when up to k rock cells may be drilled, by brute force: try every set of at most k rock cells, drill
them, and run a plain BFS. Correct, and the number of sets explodes with k."""
from collections import deque
from itertools import combinations
from math import comb

MINE = [".#.#...",
        ".#...#.",
        "...##..",
        "...##.#",
        ".###..#",
        ".##.#.."]


def plain_bfs(grid):
    """Fewest steps from the top-left to the bottom-right cell over open cells, or -1."""
    rows, cols = len(grid), len(grid[0])
    dist = [[-1] * cols for _ in range(rows)]
    dist[0][0] = 0
    queue = deque([(0, 0)])
    while queue:
        r, c = queue.popleft()
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == "." and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
    return dist[rows - 1][cols - 1]


def by_brute_force(grid, k):
    rocks = [(r, c) for r, row in enumerate(grid) for c, x in enumerate(row) if x == "#"]
    best, searches = -1, 0
    for size in range(k + 1):
        for drilled in combinations(rocks, size):
            opened = [list(row) for row in grid]
            for r, c in drilled:
                opened[r][c] = "."
            searches += 1
            d = plain_bfs(["".join(row) for row in opened])
            if d != -1 and (best == -1 or d < best):
                best = d
    return best, searches


rocks = sum(row.count("#") for row in MINE)
print(f"The mine: {len(MINE)} x {len(MINE[0])} cells, {rocks} of them rock")
for k in range(4):
    best, searches = by_brute_force(MINE, k)
    print(f"  k = {k}: {best} steps, after {searches:,} {'search' if searches == 1 else 'searches'}")
print(f"A 40 x 40 mine with 480 rock cells and k = 5: {sum(comb(480, s) for s in range(6)):,} searches")

The mine: 6 x 7 cells, 16 of them rock
  k = 0: 17 steps, after 1 search
  k = 1: 13 steps, after 17 searches
  k = 2: 11 steps, after 137 searches
  k = 3: 11 steps, after 697 searches
A 40 x 40 mine with 480 rock cells and k = 5: 210,147,849,977 searches

The searches grow like the number of sets: 1, 17, 137 and 697 for k up to 3. A 40 × 40 mine with 480 rock cells and k = 5 needs 210,147,849,977 of them, each a search of up to 1,600 cells, and k can be in the hundreds.

What to notice

The cell alone does not decide what the robot can do next: the drills it has left matter too. A robot at a cell with two drills left can follow routes that the same robot with none cannot. Make the drills left part of the node, and the problem becomes a plain BFS over at most rows × cols × (k + 1) states, each reached at most once. Keys work alike: a robot that holds the key to a door has moves that one without it lacks, so the set of keys held joins the state.

The state: row, column and drills left Pro: opens with a Pro, Premium or Ultimate pass