Show problems as
Classic problem #286MediumArrayBreadth-First SearchMatrix

Walls and Gates

Real-world version: Steps to the Nearest Dock
Tracked in this browser only
Read Walls and Gates on LeetCode(opens in a new tab)

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

A warehouse floor is stored as the m x n grid rooms. Every cell holds one of three values:

  • -1 means a rack stands there and nothing can pass through it.
  • 0 means a charging dock sits there.
  • 2147483647 means open aisle.

A trolley moves between cells that share an edge, never diagonally and never into a rack. One move counts as one step.

Fill in every open aisle cell with the number of steps on a shortest walk from that cell to any charging dock. If no dock can be walked to from a cell, leave that cell holding 2147483647. Rack cells and dock cells keep the values they already hold.

Rewrite rooms in place rather than building a new grid, and return the same grid you were handed so the result can be read back.

Examples

Example 1

Input
rooms = [[0,2147483647,2147483647,0]]
Output
[[0, 1, 1, 0]]

The second cell is one step from the dock on its left and the third cell is one step from the dock on its right.

Example 2

Input
rooms = [[2147483647,2147483647,2147483647],[2147483647,-1,2147483647],[2147483647,2147483647,0]]
Output
[[4, 3, 2], [3, -1, 1], [2, 1, 0]]

The only dock is the bottom-right cell and a rack sits in the centre. Reading the grid back, the top-left cell ends up four steps away and the cell above the dock one step away.

Example 3

Input
rooms = [[0,-1,2147483647]]
Output
[[0, -1, 2147483647]]

The rack cuts the third cell off from the dock, so that cell keeps 2147483647.

Example 4

Input
rooms = [[2147483647,-1]]
Output
[[2147483647, -1]]

There is no dock anywhere on this floor, so the open cell keeps 2147483647 and the rack is left alone.

Constraints

  • m == rooms.length
  • n == rooms[i].length
  • 1 <= m, n <= 250
  • rooms[i][j] is -1, 0, or 2147483647.

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 walls_and_gates(rooms: list[list[int]]) -> list[list[int]]:
Java
public int[][] wallsAndGates(int[][] rooms)

More on the same topics