Fewest Obstacles to Cross
Move from the top-left cell to the bottom-right cell, stepping up, down, left or right.
Cells holding 1 are obstacles and entering one costs 1 removal; cells holding 0 are free.
Print the fewest removals needed.
The starting cell counts if it is an obstacle.
0 1 1
1 1 0 -> 2
1 1 0
## Why this is not a grid DP
Every grid DP so far has restricted movement to right and down, which makes the cells order themselves: a cell depends only on cells above and to the left.
Here movement is in all FOUR directions, so a cell can depend on a neighbour that depends on it. There is no fill order, and the table has nothing to iterate over.
What there is instead is a shortest-path problem on a graph whose nodes are cells and whose edge weights are 0 for stepping onto a free cell and 1 for stepping onto an obstacle.
Noticing that four-directional movement turns a DP into a graph search is the point of this problem.
## Zero-one breadth-first search
Dijkstra solves it in O(m n log(m n)). With only two edge weights there is a simpler and
faster method.
Use a DEQUE instead of a priority queue. When relaxing an edge:
weight 0 -> push to the FRONT
weight 1 -> push to the BACK
The deque then always holds at most two distinct distances, the current one at the front and
one more at the back, so it stays sorted without any comparisons. That gives O(m n).
The invariant is worth stating because it is what makes the method correct: at every moment the distances in the deque are non-decreasing from front to back and span at most two values.
## Why the front and back must not be swapped
Pushing a zero-weight move to the back breaks the ordering and the algorithm becomes an ordinary breadth-first search over edges, which minimises the number of STEPS rather than the number of obstacles.
0 1 1 1 / 1 1 1 1 / 1 1 1 0 answers 4, and a step-minimising search returns the length of
the shortest route instead, which on this grid is a different number.
## The starting cell
The distance to the start is g[0][0], not 0. If the start is an obstacle it must be
removed to stand there.
1 as a one-cell grid answers 1, and 0 answers 0. That pair is the test.
## The alternative worth knowing
A plain Dijkstra with a priority queue gives the same answer and is the right thing to reach for when the weights are not just 0 and 1. It was the oracle these expected outputs were checked against, precisely because it shares no reasoning with the deque trick.
## Cost
Time O(m n). Space O(m n).