hardGraphsPure DSA~30 min
Fewest Obstacles to Clear a Grid Route
A maintenance bot crosses a floor grid from the top-left to the bottom-right. Empty cells are free to enter; obstacle cells can be cleared at a cost of one each. Minimize the number of obstacles cleared.
Problem
Given an m x n grid where 0 is empty and 1 is an obstacle, you move up/down/left/right and may remove obstacles. Return the minimum number of obstacles you must remove to travel from (0,0) to (m-1,n-1).
Input
An m x n binary grid (0 empty, 1 obstacle).
Output
An integer: the minimum obstacles removed.
Constraints
- 1 <= m, n <= 100000 with m * n <= 200000
- grid[i][j] is 0 or 1; grid[0][0] and grid[m-1][n-1] are 0.
Examples
Example 1
Input
grid = [[0,1,1],[1,1,0],[1,1,0]]
Output
2
Two obstacles must be removed to reach the bottom-right.
Example 2
Input
grid = [[0,0,0],[0,0,0],[0,0,0]]
Output
0
A clear path exists.