For each cell in a binary matrix, compute the distance to the nearest cell containing 0.
Problem
Given an binary matrix, return a matrix of the same size where each cell contains the minimum number of moves needed to reach any cell with value 0.
You may move one step at a time in the four cardinal directions: up, down, left, and right.
The distance for a cell that is already 0 is 0.
Goal
Produce a matrix where each entry is the shortest distance from that position to the nearest zero in the original grid.
Input Format
- A 2D binary matrix
matof sizem x n. - Each cell contains either
0or1.
Output Format
- Return a 2D integer matrix of the same size.
ans[i][j]should equal the minimum Manhattan distance frommat[i][j]to any0cell.
Constraints
- The matrix is non-empty.
- Movement is allowed only in 4 directions.
- Distances are measured in number of steps.
- The output dimensions must match the input dimensions.
Example 1
Input
mat = [[0,0,0],[0,1,0],[1,1,1]]
Output
[[0,0,0],[0,1,0],[1,2,1]]
Explanation
The center cell is one step from a zero. The bottom-middle cell is two steps away, while the bottom-left and bottom-right cells are one step away.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.