Demolition Shortcut
HardGraphs
Problem
A rescue robot must cross a building floor plan grid from the top-left cell to the bottom-right cell. 0 is a free cell and 1 is a wall. Each move goes one cell up, down, left or right.
The robot carries k demolition charges: entering a wall cell uses one charge (the wall is gone for that move). Return the minimum number of moves to reach the bottom-right cell, or -1 if it is impossible with at most k charges.
Example 1
- Input:
- grid = [[0,0,0,0],[1,1,1,0],[0,0,0,0],[0,1,1,1],[0,0,0,0]], k = 1
- Output:
- 7
Blast (1,0) and walk straight down the left column, then along the bottom row: 4 + 3 = 7 moves.
Example 2
- Input:
- grid = [[0,0,0,0],[1,1,1,0],[0,0,0,0],[0,1,1,1],[0,0,0,0]], k = 0
- Output:
- 13
Without charges the robot has to follow the zigzag corridor.
Example 3
- Input:
- grid = [[0,1,1],[1,1,1],[1,1,0]], k = 1
- Output:
- -1
Every route crosses at least three walls.
Constraints
- 1 ≤ rows, cols ≤ 40
- 0 ≤ k ≤ rows · cols
- grid[r][c] is 0 or 1
- grid[0][0] = grid[rows-1][cols-1] = 0
Hint
Show the first hint
A plain BFS over cells is not enough: reaching a cell with more charges left can be worth more than reaching it sooner.
Walkthrough
How to approach it
01Clarify before coding
- Does entering a wall cost one charge regardless of direction? Yes, one charge per wall cell entered.
- Are the start and target always free? Yes.
- Can k exceed what is ever needed? Yes; the answer is then simply the Manhattan distance.
02Brute force
Try every subset of at most k walls to remove and run a BFS on each modified grid.
Cost: C(W, k) subsets of the W walls, each with an O(r · c) BFS: astronomically large even for small k.
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.
This problem is part of Pro.