Prepare the Bunnies' Escape

Created: Jul 20, 2025

Last modified: Oct 12, 2026

TL, DR.

Show challenge description

The bunnies are about to make a run for it, but the station's halls are a maze. We get a map of 0s (corridor) and 1s (wall), with the exit in the top-left corner and the escape pod in the bottom-right one. We need the shortest path, with a twist: as part of the "remodeling", we're allowed to knock down one wall, at most. Length is measured in cells, counting both the first and the last one.

Without the wall, this would be the classic shortest path on a grid: one breadth-first search (BFS) and done. The question is how to fit that one removable wall into the picture.

# The obvious idea

Remove each wall in turn, run the search, keep the best result. It works, and with 20×20 maps it even runs in time: roughly 400 searches over 400 cells. But it's a lot of repeated work. Every search walks through nearly the whole maze again, even though only one cell changed.

# Two searches, one from each door

Picture a path that knocks down a wall. It splits into two stretches that don't cross any wall: from the exit to the wall, and from the wall to the pod. And a BFS already walks right past every wall it can reach: each time it expands a cell, it looks at the four neighbors, and some of them are walls. Instead of ignoring them, we can take note.

The minus one is there because both notes count the wall itself, and you only step on it once. A wall that one of the searches never reaches has no way in or no way out, so its weight is ∞. And there's no need to compare notes from the same search: BFS reaches cells in order of distance, so the first time it bumps into a wall is already the cheapest.

The answer is the smaller of the path that breaks nothing ($d_A$ at the pod) and the weight of the lightest wall. Just two searches, and the walls get weighed along the way: O(w·h), instead of one search per wall.

Watch it step by step. Each step explores one cell (solid) and adds its new neighbors to the frontier (dashed); the cells already explored turn blue. The search from A is drawn in purple, and when it finishes the board clears so the search from B can draw its own, in pink. The walls each step bumps into get an orange outline. On corridors, the number in the top-left corner (purple) is the distance from A and the one in the bottom-right corner (pink) is the distance from B. On walls, those corners hold each search's note, and the weight shows up in the middle. When both searches finish, only the path keeps its numbers, in order, and the wall worth knocking down blows up. The marks under the slider jump to the start of each search and to the final path, and the button plays it all on its own. Tap any cell to flip it between wall and corridor.

Legend: Wall Being explored by the search from A Being explored by the search from B Next in line (the frontier), from A and from B Already explored by the current search Wall the current cell bumps into: it gets its note or its weight

In the starting map, without knocking anything down, the corridors zigzag and the path takes 27 cells. The wall at (4, 10) changes that: the search from A reaches it for 17, the one from B for 3, so its weight is 17 + 3 − 1 = 19. Eight cells saved by one wall.

# The secret test cases

Foobar showed you two examples and kept the rest of the tests hidden. But someone (mfe5003) found a way to get them out, and posted them as terminal screenshots in this article. I transcribed them, and here are all ten cases for this challenge. Every wall shows its weight in the top-left corner. The one worth knocking down blows up, and the path gets highlighted with each cell's position along it. You can tap cells here too to edit the map.

Shortest path: 47, knocking down wall (9, 8).

# The code

When I solved this one, over six years ago, I used two searches with a hand-rolled priority queue and quite a lot more code. This is the same idea, cleaned up:

from collections import deque

INF = float('inf')
MOVES = ((-1, 0), (1, 0), (0, -1), (0, 1))


def neighbors(maze, row, col):
    for dr, dc in MOVES:
        r, c = row + dr, col + dc
        if 0 <= r < len(maze) and 0 <= c < len(maze[0]):
            yield r, c


def search(maze, start):
    """BFS from start, counting cells. Returns the distance to every open cell it reaches,
    plus every wall it bumps into with what it would cost to get there (the wall included)."""
    cost = [[INF] * len(maze[0]) for _ in maze]
    cost[start[0]][start[1]] = 1
    walls = {}
    frontier = deque([start])
    while frontier:
        row, col = frontier.popleft()
        for r, c in neighbors(maze, row, col):
            if maze[r][c] == 1:
                # walls are never added to the frontier; the first bump is already the cheapest
                walls.setdefault((r, c), cost[row][col] + 1)
            elif cost[r][c] == INF:
                cost[r][c] = cost[row][col] + 1
                frontier.append((r, c))
    return cost, walls


def solution(maze):
    height, width = len(maze), len(maze[0])
    start, goal = (0, 0), (height - 1, width - 1)
    from_start, walls_a = search(maze, start)
    _, walls_b = search(maze, goal)

    best = from_start[goal[0]][goal[1]]  # without removing anything
    for wall, cost_b in walls_b.items():
        if wall in walls_a:
            # both searches counted the wall itself, so it's subtracted once
            best = min(best, walls_a[wall] + cost_b - 1)
    return best

# Wrapping up

"You may knock down one wall" sounds like you have to try every option. The trick is to split the path at the point where something special happens and solve each half separately, once, for everything. Searching from both ends is a tool worth keeping handy: it pays off whenever a path has to go through "some point in the middle" that you don't know yet.