Distance of Nearest Cell Having One

Given a rectangular binary grid containing at least one 1, return a same-shape matrix with the distance from every cell to its nearest 1. For cell (row, col)…

Given a rectangular binary grid containing at least one 1, return a same-shape matrix with the distance from every cell to its nearest 1. For cell (row, col) and source (sr, sc), distance is |row-sr| + |col-sc|. A move goes up, right, down or left by one cell; there are no obstacles or diagonal moves. Every source 1 has distance 0 to itself. Do not modify the input grid.

1 <= number of rows, number of columns <= 500. Every cell is the integer 0 or 1. At least one cell contains 1. The visualizer accepts at most 8 rows and 8 columns to bound copied teaching snapshots. Run and Submit retain the full 500×500 domain.

Example 1: input grid = [[0,1,1,0],[1,1,0,0],[0,0,1,1]]; output [[1,0,0,1],[0,0,1,1],[1,1,0,0]]. Each source 1 has distance 0. Every zero cell in this example has an orthogonally adjacent source, so its distance is 1.

Example 2: input grid = [[1,0,1],[1,1,0],[1,0,0]]; output [[0,1,0],[0,0,1],[0,1,2]]. Cell (2, 2) needs two orthogonal steps to a source, while cells (0, 1), (1, 2) and (2, 1) need one.

Category: Graphs. Topic: graph. Difficulty: Medium. Patterns: graph-traversal.