Walls and Gates

Medium

The problem

rooms is a grid. -1 is a wall, 0 is a gate, and 2147483647 (call it INF) is an empty room. Change the grid in place so that every empty room holds the number of steps to its nearest gate, moving up, down, left or right and never through walls. A room that no gate can reach stays INF.

Example 1
Input: rooms = [[INF, -1, 0, INF], [INF, INF, INF, -1], [INF, -1, INF, -1], [0, -1, INF, INF]]
Output: rooms becomes [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]
For example the room at row 0, column 3 is one step from the gate at row 0, column 2. The room at row 3, column 3 is 4 steps from the same gate.
Example 2
Input: rooms = [[0, -1], [INF, INF]]
Output: rooms becomes [[0, -1], [1, 2]]
The gate is at the top left. The bottom-left room is 1 step away and the bottom-right room is 2 steps away.

Limits

1 ≤ rows, columns ≤ 250
Each cell is -1, 0 or 2147483647
The function returns nothing; it edits rooms

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Instead of searching from every room to a gate, search from every gate outward at once.

The idea

Multi-source BFS: push all gates (distance 0) into the queue, expand to neighbouring empty rooms setting distance+1.

Target: O(m·n) time

Go function shape

func wallsAndGates(rooms [][]int)

Reference solution

Tested with go test. Try it yourself first, then compare.

// WallsAndGates fills every empty room (2147483647) with its distance to the nearest gate (0). Walls are -1.
// Search from ALL gates at once: a multi-source BFS expands one ring per step, so the first time a room is
// reached is by its nearest gate.
func WallsAndGates(rooms [][]int) {
	const empty = 2147483647
	type cell struct{ r, c int }
	var queue []cell
	for r := range rooms {
		for c := range rooms[r] {
			if rooms[r][c] == 0 {
				queue = append(queue, cell{r, c})
			}
		}
	}
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
			r, c := cur.r+d[0], cur.c+d[1]
			if r >= 0 && c >= 0 && r < len(rooms) && c < len(rooms[0]) && rooms[r][c] == empty {
				rooms[r][c] = rooms[cur.r][cur.c] + 1
				queue = append(queue, cell{r, c})
			}
		}
	}
}

Read the lesson: Graphs: BFS / DFS / Topological Sort