Minimum Obstacle Removal to Reach Corner

In grid, 0 is an empty cell and 1 is an obstacle. You may remove obstacles to turn their cells into empty cells. Move between empty cells that share an edge, going up, down, left, or right. Return the fewest obstacles that must be removed to create a path from the top-left cell to the bottom-right cell. Both endpoint cells are initially empty.

Hatched cells show a path requiring the fewest obstacle removals.

Example 1:

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

Output: 0

Explanation: Move right and then down through empty cells. No obstacle needs to be removed.

Example 2:

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

Output: 1

Explanation: Both possible first steps enter an obstacle. Removing either of those obstacles opens a path to the destination, so the answer is 1.

Example 3:

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

Output: 2

Explanation: The grid has only one row, so every path must cross both middle cells. Both obstacles must be removed, giving 2.

Constraints:

• Each dimension is between 1 and 100000; all rows have equal length.
• 2 <= grid.length * grid[0].length <= 100000
• Each entry is either 0 or 1.
• The top-left and bottom-right entries are both 0.