2290. Minimum Obstacle Removal to Reach Corner - Detailed Explanation

Problem Statement

You are given a 2D grid of size m x n where each cell contains either 0 or 1. A cell with value 0 means that it is free to pass through, while a cell with value 1 represents an obstacle. Starting from the top-left cell (0, 0), your goal is to reach the bottom-right cell (m - 1, n - 1) while removing as few obstacles as possible. Moving to an adjacent cell (up, down, left, or right) is allowed. If you pass through an obstacle, you incur a cost of 1 for removing it. The task is to determine the minimum cost (i.e., the minimum number of obstacles that need to be removed) to reach the destination.

Example Inputs, Outputs, and Explanations

Example 1

Input:

grid = [
  [0, 1, 1],
  [1, 1, 0],
  [1, 1, 0]
]

Output:

2

Explanation:

• Starting at (0, 0) which is free (0), one optimal path is to move right to (0, 1) (an obstacle, cost = 1), then right to (0, 2) (another obstacle, cost = 2), then down to (1, 2) (free), and finally down to (2, 2) (free).
• The total cost incurred is 2 obstacle removals.

Example 2

Input:

grid = [
  [0, 1, 0, 0],
  [0, 1, 0, 1],
  [0, 0, 0, 0],
  [1, 1, 1, 0]
]

Output:

0

Explanation:

• A free path exists: starting from (0, 0), move down to (1, 0), then down to (2, 0), right to (2, 1), right to (2, 2), right to (2, 3), and finally down to (3, 3).
• No obstacles are encountered along this path, so the minimum cost is 0.

Hints for the Approach

1. Graph Representation:
   Treat each cell as a node in a graph. Moving from one cell to an adjacent cell has a cost: 0 if the adjacent cell is free (0), or 1 if it contains an obstacle (1).

2. 0-1 BFS (Deque Method):
   Since the edge weights are only 0 and 1, the 0-1 BFS algorithm is ideal. Using a deque allows you to process moves with 0 cost immediately (by adding them to the front) and delay moves that cost 1 (by adding them to the back).

3. Cost Tracking:
   Maintain a cost (or distance) matrix to record the minimum cost required to reach each cell from the start.

Approach: 0-1 BFS

Explanation

1. Initialization:

   • Create a cost matrix of the same dimensions as the grid, initializing all values to infinity (or a very large number) except for the starting cell (0, 0) which is set to 0.
   • Use a deque to manage cells to process, starting by adding the starting cell (0, 0).

2. Processing Cells:

   • At each step, pop a cell (i, j) from the front of the deque.

   • For each of the four possible moves (up, down, left, right), compute the neighbor's coordinates.

   • If the neighbor is within the grid bounds, calculate the new cost:

     • If the neighbor is free (0), the cost remains the same.
     • If the neighbor is an obstacle (1), the cost increases by 1.

   • If the new cost is lower than the previously recorded cost for the neighbor, update the cost matrix.

     • For a move that costs 0, add the neighbor to the front of the deque.
     • For a move that costs 1, add the neighbor to the back of the deque.

3. Termination:

   • Continue the process until the deque is empty. The answer will be the value in the cost matrix at the destination cell (m - 1, n - 1).

Visual Walkthrough

Imagine the grid as a landscape where each cell is a room and doors connect adjacent rooms. Some doors are locked (obstacles) and require a key (incur a cost of 1) to open, while others are open. You want to reach the exit with the minimum number of keys used. With 0-1 BFS, you always try to go through open doors first, and only use keys when absolutely necessary, ensuring that the first time you reach the exit, you’ve used the fewest keys possible.

Code Implementation

Python Code