Find Each Cell's Nearest Source

Given an m x n grid containing 1 for source cells and 0 for regular cells, compute for every cell the shortest 4-directional distance to any source cell. Moving up, down, left, or right costs 1 step. Return an m x n matrix of distances, where every source cell has distance 0. If the grid contains no source cells, return -1 for every cell.

Find Each Cell's Nearest Source

Given an m x n grid where 1 represents a source cell and 0 represents a regular cell, compute the shortest distance from every cell to any source cell. You may move up, down, left, or right, and each move costs 1 step. Return an m x n matrix of distances. Every source cell has distance 0. If the grid contains no source cells, return -1 for every cell. If the grid is empty, return an empty list.

Constraints

• 0 <= m
• 0 <= n
• 0 <= m * n <= 100000
• grid[i][j] is either 0 or 1
• All rows in grid have the same length

Examples

Example 1

Input: ([[0,0,0],[0,1,0],[0,0,0]],)
Output: [[2,1,2],[1,0,1],[2,1,2]]

Explanation: The source is in the center. Each cell's distance is its Manhattan distance to the center source.

Example 2

Input: ([[1,0,0],[0,0,0],[0,0,1]],)
Output: [[0,1,2],[1,2,1],[2,1,0]]

Explanation: There are two sources. Each cell uses the shorter distance to either the top-left or bottom-right source.

Hints

1. Instead of running a search from every regular cell, consider starting from all source cells at the same time.
2. A breadth-first search processes cells in increasing distance order when every move has the same cost.