Walls And Gates

The problem

rooms is a grid. Each cell holds -1 for a wall, 0 for a gate or 2147483647 for an empty room. A step goes from a cell to the cell directly above, below, left or right of it, and never into a wall. Replace the value of every empty room with the number of steps to its nearest gate. An empty room that no gate can reach keeps 2147483647. Return the grid.

What to write

function solve(rooms: number[][]): number[][]

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

Output
[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

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

Output
[[2147483647,-1,0]]

Constraints

Return the updated rectangular grid.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The three values cannot be confused: a wall is -1, a gate is 0, and 2147483647 is far larger than any real distance in a grid. So a cell that still holds 2147483647 is a room nobody has filled yet. The grid itself can tell you which rooms are done.

2. Hint 2: Ask a smaller question

   Picture one row: gate, room, room, room, gate. Fill in the three distances by hand. Which rooms could you fill first, and what did you need to know before you could fill the middle one?

3. Hint 3: Name the pattern

   Rooms next to a gate get 1, the unfilled rooms next to those get 2, and so on. Spreading outwards from all the gates at once, one step at a time, is breadth-first search by distance. The signal is a shortest distance, counted in steps, to the nearest of several starting points. Read the lesson on breadth-first search by distance.

4. Hint 4: State the invariant

   Keep the cells to spread from in a queue: a line where you add at the back and take from the front. Cells leave it in order of distance, nearest first. So the first time an empty room is reached, the number written into it is its shortest distance, and it never changes again.

5. Hint 5: Sketch the pseudocode

   Add every gate to a queue. While the queue is not empty: take the front cell. For each of the four cells next to it that is inside the grid and still holds 2147483647: write the front cell's value plus 1 into that cell and add it to the back. Return the grid.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Run one multi-source breadth-first search from all gates. The first visit to a room gives its shortest distance.

The slow way

Handle one gate at a time. From each gate, walk outwards through the rooms, work out every room's distance from that gate, and keep the smaller number when a room already has one. It is correct, but every gate sweeps the grid again. With many gates the work is about the number of gates times the number of cells.

The insight

A room next to a gate is 1 step away, an unfilled room next to that one is 2 steps away, and so on. If all the gates spread outwards together, one step at a time, the first number to reach a room comes from its nearest gate. So each room is written once. This nearest-first spreading is called breadth-first search.

Step by step

1. Put every gate in a queue. A queue is a line: you add at the back and take from the front. Every gate is a starting point at distance 0, and the grid already holds 0 there. With all the gates waiting first, they spread together.
2. Take the cell at the front: the grid already holds its distance. Cells leave the queue in the order they were filled, so nearer cells come out before farther ones. A room is filled before it joins the queue, so its distance can be read from the grid.
3. Look at the four cells next to it. One step goes to the cell directly above, below, left or right. Some of these four positions may lie outside the grid; the test in the next step leaves those out.
4. A room still marked empty is one step farther: fill it and queue it. No gate has reached this room yet, so the way through the cell taken out is a shortest one. Writing the distance also marks the room as done, because only a room that still holds 2147483647 is ever filled.
5. Return the grid with the distances written in. Every room that some gate can reach has been filled by now. A room that still holds 2147483647 was never reached, and the problem says such a room keeps that value.

The same numbered steps are the comments in each solution.

function solve(rooms) {
  // 1. Put every gate in a queue
  // The queue is an array of [row, column]. Removing the first item of an
  // array is slow, so nothing is removed: it is read in order instead.
  const q = [];
  for (let r = 0; r < rooms.length; r++)
    for (let c = 0; c < rooms[0].length; c++)
      if (rooms[r][c] === 0) q.push([r, c]);
  // 2. Take the cell at the front: the grid already holds its distance
  // i is the position of the front of the queue; push adds at the back.
  for (let i = 0; i < q.length; i++) {
    const [r, c] = q[i];
    // 3. Look at the four cells next to it
    for (const [a, b] of [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ])
      // 4. A room still marked empty is one step farther: fill it and queue it
      // A cell outside the grid reads as undefined, which is not 2147483647.
      if (rooms[a]?.[b] === 2147483647) {
        rooms[a][b] = rooms[r][c] + 1;
        q.push([a, b]);
      }
  }
  // 5. Return the grid with the distances written in
  return rooms;
}

function solve(rooms: number[][]): number[][] {
  // 1. Put every gate in a queue
  // The queue is an array of [row, column]. Removing the first item of an
  // array is slow, so nothing is removed: it is read in order instead.
  const q: number[][] = [];
  for (let r = 0; r < rooms.length; r++)
    for (let c = 0; c < rooms[0].length; c++)
      if (rooms[r][c] === 0) q.push([r, c]);
  // 2. Take the cell at the front: the grid already holds its distance
  // i is the position of the front of the queue; push adds at the back.
  for (let i = 0; i < q.length; i++) {
    const [r, c] = q[i];
    // 3. Look at the four cells next to it
    for (const [a, b] of [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ])
      // 4. A room still marked empty is one step farther: fill it and queue it
      // A cell outside the grid reads as undefined, which is not 2147483647.
      if (rooms[a]?.[b] === 2147483647) {
        rooms[a][b] = rooms[r][c] + 1;
        q.push([a, b]);
      }
  }
  // 5. Return the grid with the distances written in
  return rooms;
}

from collections import deque


def solve(rooms):
    # 1. Put every gate in a queue
    rows, cols = len(rooms), len(rooms[0])
    # The value that marks an empty room.
    empty = 2147483647
    # A deque is a list that is fast at both ends: append adds at the back,
    # popleft takes from the front. Each entry is (row, column).
    queue = deque()
    for r in range(rows):
        for c in range(cols):
            if rooms[r][c] == 0:
                queue.append((r, c))
    # 2. Take the cell at the front: the grid already holds its distance
    while queue:
        r, c = queue.popleft()
        # 3. Look at the four cells next to it
        for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
            # 4. A room still marked empty is one step farther: fill it and queue it
            # The two 0 <= checks matter: Python reads row -1 as the last row.
            if 0 <= nr < rows and 0 <= nc < cols and rooms[nr][nc] == empty:
                rooms[nr][nc] = rooms[r][c] + 1
                queue.append((nr, nc))
    # 5. Return the grid with the distances written in
    return rooms

Example 1, traced

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

Output
[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Why it works

Cells leave the queue in order of distance: all the gates, then every room at distance 1, then distance 2, and so on. So when an empty room is first reached, no cell with a smaller distance is next to it, or that cell would have filled it earlier. One more than the reaching cell's distance is therefore the shortest, and a filled room is never changed again.

Time and space

Time O(rows · cols), extra space O(rows · cols). The scan reads every cell once. Each cell joins the queue at most once and looks at four cells when it is taken out, so the time is O(rows · cols). The queue can hold every cell of the grid, so the space is O(rows · cols).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Spread only into a room that still holds 2147483647. If the test accepts every grid cell that is not a wall, gates and filled rooms are overwritten and queued again and again, and on example 1 the loop never ends.
• Put all the gates in the queue before you take anything out. If one gate's spread is finished before the next gate begins, rooms keep the first gate's distance: example 1 gives the top-left room 4 instead of 3.
• Return the grid at the end. The value you return is what gets compared with the expected grid, so a function that fills rooms correctly and returns nothing fails every test.

Pattern

Breadth-first search by distance. Builds on Rotting Oranges.

Keep going