Skip to content
AI360Xpert
Back to Graphs
Medium

Walls and Gates

You are given an `m x n` grid `rooms` initialized with these three possible values. - `-1` A wall or an obstacle. - `0` A gate. - `INF` Infinity means an empty room. We use the value `2147483647` (2^31 - 1) as `INF` to represent infinity. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with `INF`.

Examples

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]]
The 2D grid is: INF -1 0 INF INF INF INF -1 INF -1 INF -1 0 -1 INF INF The answer is: 3 -1 0 1 2 2 1 -1 1 -1 2 -1 0 -1 3 4
Input:rooms = [[-1]]
Output:[[-1]]
The grid only contains a wall.

Constraints

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

Breadth-First Search (BFS)

Approach

1. Intuition: We need to find the shortest distance from each empty room to the nearest gate. If we start BFS from every empty room, it would be inefficient. Instead, we can start BFS from ALL gates simultaneously (multi-source BFS). 2. First, we scan the grid to find all gates (cells with value `0`) and add their coordinates to a queue. 3. We initialize our BFS queue with all the gates. Since we process the queue layer by layer, the first time we reach an empty room, we are guaranteed to have found the shortest path to it from a gate. 4. We define the 4 possible directions (up, down, left, right). 5. While the queue is not empty, we pop a cell `(r, c)`. 6. For each neighbor of `(r, c)`, if it is out of bounds or NOT an empty room (meaning it's a wall, another gate, or an already visited empty room), we skip it. 7. Otherwise, the neighbor is an unvisited empty room. Its distance to a gate is the distance of `(r, c)` plus 1. We update the neighbor's value in the grid and push it into the queue for further exploration. 8. We repeat this until the queue is empty. The grid is modified in-place with the shortest distances.

Complexity Analysis

Time Complexity
O(m * n)
Space Complexity
O(m * n)

Time complexity is O(m * n) because we visit each cell at most once. Space complexity is O(m * n) since the queue could contain at most m * n elements.

Solution.java
class Solution {    public void wallsAndGates(int[][] rooms) {        if (rooms == null || rooms.length == 0) return;                int m = rooms.length;        int n = rooms[0].length;        Queue<int[]> queue = new LinkedList<>();                // Find all gates and add them to the queue        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (rooms[i][j] == 0) {                    queue.offer(new int[]{i, j});                }            }        }                int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};                // Multi-source BFS        while (!queue.isEmpty()) {            int[] curr = queue.poll();            int r = curr[0];            int c = curr[1];                        for (int[] dir : dirs) {                int nr = r + dir[0];                int nc = c + dir[1];                                // If out of bounds or not an empty room, skip                if (nr < 0 || nr >= m || nc < 0 || nc >= n || rooms[nr][nc] != Integer.MAX_VALUE) {                    continue;                }                                // Update distance and add to queue                rooms[nr][nc] = rooms[r][c] + 1;                queue.offer(new int[]{nr, nc});            }        }    }}