Given a binary grid with R rows and C columns, cell value 0 represents empty space and cell value 1 represents a removable obstacle. Movement is allowed in four directions: right, down, left, and up.
Return the minimum number of obstacles requiring removal along any path from the upper-left corner (0,0) to the lower-right corner (R-1,C-1). Both corner cells contain 0.
Example 1
Input: grid = [[0,1,1],[1,1,0],[1,1,0]]
Output: 2
Explanation: A valid minimum route removes two obstacles before reaching the lower-right corner.
Example 2
Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
Output: 0
Explanation: An all-empty route connects both corners, so no obstacle removal is required.
Approach
Binary edge costs allow 0–1 BFS to replace the min-heap with a deque. A move costing 0 enters the front, while a move costing 1 enters the back.
Front insertion prioritizes routes requiring no additional removal and reproduces Dijkstra’s ordering for edge weights restricted to 0 and 1.
Algorithm
Initialize an
R×Cdistance matrix with infinity, set the top-left distance to0, and add{0, 0, 0}to a deque.Continue processing while the deque contains states and remove the state from the front.
Skip the removed state when the stored cost differs from the current cell distance, as the state represents an outdated route.
Return the current cost when the removed cell is the bottom-right destination.
Examine all four in-bounds neighbors and calculate the candidate cost as
currentCost+grid[nextRow][nextCol].Upon finding a smaller cost, update the neighbor distance and add the state to the deque front for cost
0or back for cost1.Return the stored destination distance after deque processing finishes.
Dry Run
minimum-obstacle-removals-01-bfs-corrected-v2
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Return the minimum obstacle removals needed for the corner path. int minimumObstacles(vector<vector<int>>& grid) { int rows = grid.size(); int cols = grid[0].size(); const int INF = 1000000000; const int directions[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} }; vector<vector<int>> dist(rows, vector<int>(cols, INF)); deque<tuple<int, int, int>> pending; // Start from the empty upper-left cell at zero cost. dist[0][0] = 0; pending.push_front({0, 0, 0}); // Process zero-cost moves before one-cost moves. while (!pending.empty()) { auto [cost, row, col] = pending.front(); pending.pop_front(); // Skip a state replaced by a cheaper route. if (cost != dist[row][col]) { continue; } // Deque order finalizes the first destination state. if (row == rows - 1 && col == cols - 1) { return cost; } // Inspect all four neighboring cells. for (const auto& direction : directions) { int nextRow = row + direction[0]; int nextCol = col + direction[1]; // Ignore coordinates outside the grid. if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) { continue; } int weight = grid[nextRow][nextCol]; int nextCost = cost + weight; // Relax a neighbor after finding a cheaper route. if (nextCost < dist[nextRow][nextCol]) { dist[nextRow][nextCol] = nextCost; // Prioritize a free cell at the deque front. if (weight == 0) { pending.push_front( {nextCost, nextRow, nextCol} ); } else { pending.push_back( {nextCost, nextRow, nextCol} ); } } } } return dist[rows - 1][cols - 1]; }};// Driver code.int main() { vector<vector<int>> grid = { {0, 1, 1}, {1, 1, 0}, {1, 1, 0} }; Solution sol; cout << sol.minimumObstacles(grid); return 0;}Complexity Analysis
Time Complexity: O(R×C), where R and C are the grid dimensions; 0–1 BFS processes the constant-degree grid graph without heap operations.
Space Complexity: O(R×C), where the distance matrix and deque can each store a number of states proportional to R×C.
Interview follow-up Questions
Entering an obstacle requires one removal, while entering an empty cell requires none.
Be the first to add a comment.