Understanding the Problem
You are given a binary grid — a 2D matrix where each cell is either 0
or 1
. Your task is to find, for every cell, the distance to the nearest cell that contains a 1
. The distance is measured in number of steps to adjacent cells (up, down, left, right only — not diagonally).
This means that if you're standing on a 0
, you want to know how far away the nearest 1
is, moving only in four directions. The output should be a new grid of the same size where each cell contains this distance value.
Step-by-Step Solution with Example
Step 1: Think in terms of distance spread
We can treat all cells with a 1
as starting points and spread outward using Breadth-First Search (BFS). This way, we fill in the nearest distance for each 0
based on how many steps it takes to reach the closest 1
.
Step 2: Initialize the result and queue
Create a result matrix of the same size initialized with -1
or Infinity
to indicate that we haven't found a distance yet. Also, create a queue and push all cells that already contain a 1
into it — these are our BFS starting points. Mark their distance as 0
in the result.
Step 3: Perform BFS from all 1s
Now we perform multi-source BFS. From each 1-cell in the queue, we explore its neighbors (up, down, left, right). If a neighboring cell hasn’t been visited yet, we set its distance to current distance + 1 and push it to the queue.
Step 4: Continue until all cells are processed
Repeat this process until the queue is empty. Each cell is guaranteed to be visited only once, and the first time it’s visited will be from the nearest 1
. This ensures optimality (shortest path).
Step 5: Final result grid
The final result grid contains, for each cell, the minimum number of steps to the nearest 1
.
Example:
Input Grid:
[
[0, 0, 1],
[0, 1, 0],
[1, 0, 0]
]
Output Distance Grid:
[
[2, 1, 0],
[1, 0, 1],
[0, 1, 2]
]
In this example, the 1
s act as sources. The zeros take increasing values as we move away from the nearest 1
. The cell [0,0] is 2 steps away from the nearest 1
— it could go down to [1,0] then right to [1,1].
Edge Cases
Case 1: All cells are 1
If every cell is a 1
, then each cell is already at distance 0. The output will be a grid filled with zeros.
Case 2: No cell contains 1
If there are no 1
s in the grid, we cannot compute distances. The output may remain as -1 or some sentinel value like Infinity
, or depending on the problem constraints, return an empty grid or an error.
Case 3: Grid contains only one 1
If there is only one 1
, the BFS will spread from that single point, and all other distances will be based on how far they are from that cell.
Case 4: Grid size is 1x1
With a single cell, either the output is 0
(if it is a 1
) or it depends on whether any 1
exists — if not, it remains unresolvable.
Finally
This problem teaches an important application of Breadth-First Search from multiple sources. The key idea is to treat all 1
s as starting points and let BFS naturally expand to fill in the shortest distance for each 0
. This approach ensures both correctness and efficiency, making it ideal for large grids as well.
Comments
Loading comments...