996. 01 Matrix — Distance to Nearest Zero

Given a matrix of 0s and 1s, return a matrix of the same size where each cell holds its distance (number of steps, moving 4-directionally) to the nearest 0. The input is JSON {mat} and is guaranteed to contain at least one 0.

Input: JSON {mat}.

Output: Nested array — the distance matrix.

Examples

Input: {"mat":[[0,0,0],[0,1,0],[1,1,1]]}
Output: [[0,0,0],[0,1,0],[1,2,1]]
Explanation: Distances to the nearest 0.

Input: {"mat":[[0]]}
Output: [[0]]
Explanation: Single zero.

Input: {"mat":[[0,1],[1,0]]}
Output: [[0,1],[1,0]]
Explanation: Each 1 is adjacent to a 0.

Constraints

• 1<=rows,cols<=10^4
• at least one 0

Asked by