A binary matrix only has 0 or 1. For every element in the matrix, find the minimum number of steps to reach 1 (left, right, down, up).
Input:
[[0, 1, 0],
[0, 0, 1],
[0, 0, 1]
]Output:
[[1, 0, 1],
[2, 1, 0],
[2, 1, 0]
]This problem asks for the minimum number of orthogonal steps from every cell in a binary matrix to the nearest 1. The standard solution is a multi-source BFS: initialize the queue with all 1-cells, expand layer by layer, and assign distances to neighboring 0-cells. This produces the shortest distance for every cell in O(mn) time.
END
