Distance to Nearest Zero

You are given a two-dimensional integer array matrix containing only 0s and 1s. Return a new matrix of the same size where each cell holds the Manhattan distance from that cell to the nearest 0 in matrix.

The Manhattan distance between cells (r1, c1) and (r2, c2) is abs(r1 - r2) + abs(c1 - c2). A cell that already holds 0 has distance 0 to itself.

You can assume matrix contains at least one 0.

Examples

Example 1

Input: matrix = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Example 2

Input: matrix = [[1,0],[1,1]]
Output: [[1,0],[2,1]]

Example 3

Input: matrix = [[0]]
Output: [[0]]