#226MediumGraphs· 0-1 BFS with a Deque

Fewest Walls to Break

A rescue drone must get from the top-left room to the bottom-right room of a collapsed building. The floor plan is a grid: `0` is an open room and `1` is a rubble wall. The drone moves between rooms that share a side (up, down, left or right) and can drill through a wall room, which removes it permanently and costs one drill charge. Moving into an open room is free. Return the minimum number of walls the drone has to drill through to reach the bottom-right room. The start and the goal rooms are always open.

Input format

`grid`: a rectangular array of 0s and 1s.

Output format

An integer: the minimum number of walls to drill.

Examples

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

Output: 2

The start room is cut off by walls on both sides. Every route must drill at least two walls, for example the rooms (0,1) and (1,1), before reaching the open rooms in the right column.

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

Output: 0

Going down, right along the open bottom row and then up the right column needs no drilling.

Input: grid = [[0]]

Output: 0

A one-room floor needs nothing.

Constraints

1 <= rows, columns <= 300
grid[r][c] is 0 or 1
grid[0][0] = grid[rows-1][columns-1] = 0

#0-1-bfs
#deque
#graph
#grid
#shortest-path