Through the Walls to the Far Corner

Hard

A warehouse floor plan is given as a grid plan with m rows and n columns: 0 is a free cell and 1 is a wall that can be knocked down. You may move up, down, left or right, through free cells only. You start at (0, 0) and want to reach (m - 1, n - 1). Return the fewest walls you must knock down to open such a path.

Example 1

plan=[[0, 1, 0], [0, 1, 0], [0, 1, 0]] → 1

The middle column is walled off from top to bottom, so one wall has to go, and one is enough.

Example 2

plan=[[0, 0, 1], [1, 0, 1], [1, 0, 0]] → 0

The free cells (0, 0) → (0, 1) → (1, 1) → (2, 1) → (2, 2) form a path with nothing to break.

Example 3

plan=[[0, 1, 1, 0]] → 2

A single-row corridor: both walls sit on the only route.

Constraints

1 ≤ m, n
2 ≤ m · n ≤ 10⁵
plan[i][j] is 0 or 1
plan[0][0] = plan[m - 1][n - 1] = 0

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Breadth-First Search Graph Array Matrix Shortest Path Heap (Priority Queue)

Similar problems

Ball Into the Hole Hard Repaint Arrows to Reach the Exit Hard Rooms on a Timer Hard Shortest Path of a Rolling Ball Medium Across the Hazard Field Medium

Input

plan=[[0, 1, 0], [0, 1, 0], [0, 1, 0]]

Expected

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