Show problems as
Classic problem #542MediumArrayDynamic ProgrammingBreadth-First SearchMatrix

01 Matrix

Real-world version: Steps to the Nearest Air Shaft
Tracked in this browser only
Read 01 Matrix on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A mine level is surveyed as a rectangular grid of cells. grid[r][c] is 0 when the cell holds a ventilation shaft and 1 when it is plain rock. At least one cell holds a shaft.

A surveyor moves between cells that share an edge, one step per move, and every cell of the level can be walked through whatever its marking. Diagonal moves are not possible.

For every cell report the fewest steps from that cell to a cell holding a shaft; a cell that holds a shaft reports 0. Return these counts in a grid of the same shape as grid.

Examples

Example 1

Input
grid = [[0, 1, 1], [1, 1, 1], [1, 1, 1]]
Output
[[0, 1, 2], [1, 2, 3], [2, 3, 4]]

The one shaft sits at row 0, column 0. The cell at row 1, column 1 reaches it with one step up and one step left, so it reports 2, and the opposite corner reports 4.

Example 2

Input
grid = [[1, 1, 0], [1, 1, 1]]
Output
[[2, 1, 0], [3, 2, 1]]

The shaft sits at row 0, column 2. The cell at row 1, column 0 walks right, right and up, so it reports 3.

Example 3

Input
grid = [[0]]
Output
[[0]]

The single cell holds a shaft, so no steps are needed.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10^4
  • 1 <= m * n <= 10^4
  • grid[i][j] is either 0 or 1.
  • There is at least one 0 in grid.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def steps_to_nearest_shaft(grid: list[list[int]]) -> list[list[int]]:
Java
public int[][] stepsToNearestShaft(int[][] grid)

More on the same topics