1067. Minimum Obstacles to Reach Corner (0-1 BFS)

Given an m x n grid where 0 is empty and 1 is an obstacle, starting at the top-left corner and moving 4-directionally, return the minimum number of obstacles you must remove to reach the bottom-right corner. The input is JSON {grid}.

Input: JSON {grid}.

Output: Integer — the minimum obstacles removed.

Examples

Input: {"grid":[[0,1,1],[1,1,0],[1,1,0]]}
Output: 2
Explanation: Two obstacles must be cleared.

Input: {"grid":[[0,1],[1,0]]}
Output: 1
Explanation: Remove one blocking cell.

Input: {"grid":[[0]]}
Output: 0
Explanation: Already at the corner.

Constraints

• 1<=rows,cols<=10^5 total

Asked by