All problems

Zero-One Matrix

Medium · graph traversal

You are given a rectangular grid mat that contains only 0 and 1. At least one cell holds 0.

For every cell, find the number of steps needed to reach the nearest cell holding 0, where each step moves up, down, left or right by one cell. A cell that holds 0 is 0 steps from itself.

Return a grid of the same size, where each cell holds that number of steps for the matching cell of mat.

Examples

Example 1

Input: mat = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]

Output: [[0, 0, 0], [0, 1, 0], [1, 2, 1]]

The middle cell is next to a 0. The bottom-middle cell needs two steps to reach the nearest 0, while the bottom corners need one.

Example 2

Input: mat = [[1, 1, 1], [1, 1, 1], [1, 1, 0]]

Output: [[4, 3, 2], [3, 2, 1], [2, 1, 0]]

The only 0 is in the bottom-right corner, so each distance is the row gap plus the column gap to it.

Constraints

• 1 <= rows, cols <= 30
• Every cell is either 0 or 1.
• There is at least one 0 in the grid.
• All rows have the same length.