01 Matrix

Given an m x n binary matrix:

• 0: A goal cell.
• 1: An empty cell.

For each cell, find the distance to the nearest 0. The distance between adjacent cells is 1.

A naive BFS from each 1 would be too slow (O((RC)^2)).

Better Approach: Multi-Source BFS

1. Reverse Thinking: Instead of finding nearest 0 from 1s, let the 0s expand outward like a flood.
2. Initialization:
   • Enqueue ALL cells containing 0 at time=0.
   • Mark all 1 cells as Infinity (unvisited).
3. Expansion: Pop a cell. Visit its unvisited neighbors. Set neighbor dist = current dist + 1. Enqueue neighbor.

Watch the '0's expand simultaneously to fill the grid.