Walls and Gates
Medium · Stack & Strings · Array · Breadth-First Search · Matrix
Problem
You are given an m x n grid rooms in which every cell is one of:
- -1: a wall,
- 0: a gate,
- 2147483647 (call it INF): an empty room.
Fill every empty room, in place, with the number of steps to its nearest gate. A step moves up, down, left or right, never through a wall. A room that cannot reach any gate keeps the value INF. Nothing is returned; the grid itself is checked.
Examples
Input: rooms = [[2147483647,-1,0],[2147483647,2147483647,2147483647]] Output: [[4,-1,0],[3,2,1]]
Distances spread from the gate in the top right, along the bottom row and around the wall.
Input: rooms = [[0,-1,2147483647]] Output: [[0,-1,2147483647]]
The wall cuts the last room off from the gate, so it keeps INF.
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]]
Each room takes the distance to whichever gate is closer.
Constraints
- m == len(rooms)
- n == len(rooms[i])
- 1 <= m, n <= 250
- rooms[i][j] is -1, 0 or 2^31 - 1
Approaches
- BFS from each gate separately — time O(g · m · n), space O(m · n)
Follow-up
Starting a BFS from many sources at once is the standard tool for "distance to the nearest X": the nearest zero in a binary matrix, how long rot takes to spread from several rotten fruits, how far a water cell is from land. The distances are exactly those of a single BFS from an imaginary super-source joined to every gate.
Related problems
Start free on Cariara · Coding problems · System design studio
