Steps to the Nearest Empty Seat

A cinema hall is a grid seats where 1 is an occupied seat and 0 is an empty seat. Every cell is a seat; there are no walls. Return a grid of the same shape where each cell holds the number of steps to the nearest empty seat, moving between side-adjacent cells. Empty seats hold 0. At least one seat is empty.

Examples

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

Input:  seats = [[0,1,1,1]]
Output: [[0,1,2,3]]

Constraints

• 1 <= rows, cols <= 60, at least one 0.
• Target O(rows * cols) time.

Goals

• Compute a distance transform over a binary grid
• Recognise that BFS from all zero cells replaces per-cell searches