Minimum Obstacle Removal to Reach Corner

Use 0-1 BFS for binary costs

Moving into an empty cell costs zero and moving into an obstacle costs one removal. Treat each cell as a graph node with four neighbors and maintain a distance matrix. Start at (0,0) with distance zero. When relaxing a neighbor, push it to the front of a deque if its entry cost is zero, otherwise push it to the back. This preserves the same nondecreasing-distance property that Dijkstra needs, but exploits the fact that weights are only zero or one. The first settled distance to the bottom-right is the minimum removals.

Avoid BFS shortcuts

Plain BFS minimizes number of steps, not obstacle count, so a longer route with fewer obstacles can be missed. A regular priority-queue Dijkstra is correct but unnecessary overhead. Only update and enqueue a neighbor if the proposed distance improves; otherwise cycles create needless work. Each edge is relaxed a constant number of times, so time is O(rows*cols) and space is O(rows*cols). Test a clear path, a grid whose start or end is an obstacle under the statement's convention, one row, and a case where the direct path has more obstacles than a detour.