Fewest Walls to Break

MediumAdvanced Graphs

Problem

A rescue robot stands at the top-left cell of a collapsed building plan grid, where 0 is open floor and 1 is a wall. It must reach the bottom-right cell, moving up, down, left or right. The robot can break through a wall, which turns that cell into open floor.

Return the minimum number of walls the robot must break. The start and goal cells are always open.

Example 1

Input:
grid = [[0,1,1],[1,1,0],[1,1,0]]
Output:
2

Every neighbour of the start is a wall, and every cell one wall away still borders only walls on the way, so two walls are needed (e.g. right twice, then down twice).

Example 2

Input:
grid = [[0,0],[0,0]]
Output:
0

Constraints

  • 1 ≤ rows, cols ≤ 200
  • grid[r][c] ∈ {0, 1}
  • grid[0][0] = grid[rows-1][cols-1] = 0

Hint

Show the first hint

Entering an open cell costs nothing; entering a wall costs one break.

Walkthrough

How to approach it

01Clarify before coding

  • Does the cost depend on the cell entered or the move made? On the cell entered: a wall costs 1.
  • Diagonal moves? No.
  • Is the goal always reachable? Yes, since any wall can be broken.

02Brute force

Try breaking every subset of walls, then BFS to check connectivity.

Cost: 2^(walls) subsets: impossible beyond tiny grids.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.