Minimum Cost Path in Grid with Cell Flipping

Problem Statement

You are given a grid of 0s and 1s of size n x m. You can change a 1 to a 0 at a cost of 1. Moving through a 0 cell is free.

Find the minimum cost to travel from the top-left cell (0,0) to the bottom-right cell (n-1, m-1). You can move in 4 directions.

Constraints

• 1 <= n, m <= 1000
• Grid cells are 0 or 1
• Movement is 4-directional

Example

Input:

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

Output: 1

Explanation: Path (0,0)→(0,1 flip, cost 1)→(0,2)→(1,2)→(2,2). Or go down and around. Minimum flips needed = 1.

What the Interviewer Expects

1. Recognize it's a shortest-path problem where edge cost = the cost of entering a cell (1 if it's a 1, 0 if it's a 0).
2. 0-1 BFS is optimal — since edge weights are only 0 or 1, use a deque:
   • Moving to a 0 cell → push to FRONT of deque (cost 0)
   • Moving to a 1 cell → push to BACK of deque (cost 1)
   • This gives O(n·m) instead of Dijkstra's O(n·m·log)
3. Alternatively Dijkstra — works but slower. Mention 0-1 BFS as the optimization.
4. Track minimum cost to reach each cell; skip if a cheaper path already found.

Follow-ups

1. Why is 0-1 BFS faster than Dijkstra here? When can you use it?
2. What if flipping had variable costs (not always 1)?
3. What if you could move in 8 directions (including diagonals)?
4. What if you're limited to at most K flips total?