Walls and Gates

XXX. Walls and Gates

Matrix

BFS

Problem Statement:

You are given an m x n grid representing a room with three possible states:

• -1: Wall or obstacle.
• 0: Gate.
• Integer.MAX_VALUE: Empty room.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should remain Integer.MAX_VALUE.

Algorithm:

1. Identify all gates (cells with value 0) and add them to a queue.
2. Perform a Breadth-First Search (BFS) starting from each gate:
   • Explore all four possible directions (up, down, left, right).
   • If the neighboring cell is an empty room (Integer.MAX_VALUE), update its value to the current distance and add it to the queue.
3. Continue BFS until all reachable cells have been updated.

Complexity:

Time Complexity: O(m × n), where m is the number of rows and n is the number of columns. Each cell is visited at most once.
Space Complexity: O(m × n) for the queue.

Java Implementation:

public void wallsAndGates(int[][] rooms) {
    if (rooms.length == 0) return; // Handle empty input

    int m = rooms.length;
    int n = rooms[0].length;
    Queue queue = new LinkedList<>();

    // Add all gates 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});

    // Perform BFS to calculate minimum distances
    int[] DX = {1, 0, -1, 0};
    int[] DY = {0, 1, 0, -1};
    int distance = 0;

    while (!queue.isEmpty()) {
        int size = queue.size();
        distance++;

        for (int s = 0; s < size; s++) {
            int[] curr = queue.poll();
            int currX = curr[0];
            int currY = curr[1];

            // Explore neighbors
            for (int k = 0; k < 4; k++) {
                int newX = currX + DX[k];
                int newY = currY + DY[k];

                // Update empty rooms and add to queue
                if (newX >= 0 && newX < m && newY >= 0 && newY < n && rooms[newX][newY] == Integer.MAX_VALUE) {
                    rooms[newX][newY] = distance;
                    queue.offer(new int[]{newX, newY});
                }
            }
        }
    }
}
                

Python Implementation:

from collections import deque

def wallsAndGates(rooms):
    if not rooms or not rooms[0]:
        return

    m, n = len(rooms), len(rooms[0])
    queue = deque()

    # Add all gates to the queue
    for i in range(m):
        for j in range(n):
            if rooms[i][j] == 0:
                queue.append((i, j))

    # Perform BFS
    directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            newX, newY = x + dx, y + dy
            if 0 <= newX < m and 0 <= newY < n and rooms[newX][newY] == float('inf'):
                rooms[newX][newY] = rooms[x][y] + 1
                queue.append((newX, newY))