Maze Walk With Wall Breaks

Hard

A maze is an m × n table grid: 0 is an open cell and 1 is a wall. In one step you move to a neighbouring cell up, down, left or right. You carry charges charges: one charge lets you pass through one wall cell (blowing it up). Find the fewest steps from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1) if you may break at most charges walls. If the corner cannot be reached, return -1.

Example 1

grid=[[0, 0, 0, 0], [1, 1, 1, 0], [0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0]], charges=1 → 7

Without breaking anything you would have to snake through the maze, 13 steps. Break the wall at (1, 0), walk straight down the left edge and then right along the bottom row: 4 + 3 = 7 steps.

Example 2

grid=[[0, 1, 1], [1, 1, 1], [1, 1, 0]], charges=1 → -1

Any corner-to-corner route crosses at least three walls, and there is only one charge.

Example 3

grid=[[0, 0, 0], [0, 0, 0]], charges=2 → 3

There are no walls: three steps reach the bottom-right corner.

Constraints

1 ≤ m, n ≤ 40
grid[i][j] is 0 or 1
1 ≤ charges ≤ m · n
grid[0][0] = grid[m − 1][n − 1] = 0

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Array Matrix

Similar problems

Frame Around an Ink Blot Hard A House Close to Every Building Hard Longest Uphill Walk Hard Rain Pools on a Relief Map Hard Ball Into the Hole Hard

Input

grid=[[0, 0, 0, 0], [1, 1, 1, 0], [0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0]], charges=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 73 tests on the server, hidden ones included.