847. Fewest Walls Removed
A robot vacuum cleans a rectangular floor plan stored in grid, where 0 marks a free tile and 1 marks a fallen shelf that blocks the tile. The robot starts on the top-left tile grid[0][0] and must reach the bottom-right tile, moving one tile at a time up, down, left or right.
The robot cannot enter a blocked tile, but a worker can clear any shelf beforehand. Return the smallest number of shelves that must be cleared so that some route from the top-left tile to the bottom-right tile exists. If the route is already open, the answer is 0. Both corner tiles are guaranteed to be free.
Example 1
- Input:
- grid = [[0,1,0],[0,1,0],[0,1,0]]
- Output:
- 1
- Explanation:
The middle column is blocked on every row, so crossing it costs one shelf; clearing a single shelf (for example the one at the top of the middle column) lets the robot through, and one is the minimum.
Example 2
- Input:
- grid = [[0,1,1],[1,1,0],[1,0,0]]
- Output:
- 2
- Explanation:
Both neighbours of the start are shelves and so are the tiles after them, so at least two must go; clearing the top-middle and centre shelves opens the route top-middle, centre, right edge, goal, so the answer is 2.
Example 3
- Input:
- grid = [[0,0],[1,0]]
- Output:
- 0
- Explanation:
Going right and then down uses only open cells, so nothing needs to be removed.
Constraints
- 1 ≤ grid.length, grid[0].length and grid.length * grid[0].length ≤ 106
- grid[i][j] is 0 or 1
- grid[0][0] = 0 and grid[m - 1][n - 1] = 0
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(m * n)
- Space
- O(m * n)