Walls and Gates

Problem Statement

In this problem, you are provided with a grid, termed as rooms, each cell of which can hold one of three possible values:

• -1 which indicates the presence of a wall or an obstacle that is impassable.
• 0 which denotes a gate, a point of interest from where distances are to be calculated.
• INF, representing an empty room. This is numerically depicted as 2147483647, a large number chosen to imply a 'theoretically infinite' distance since no distance in the context of the problem should reach this value.

The task is to transform each INF value in the grid such that it represents the shortest distance from that cell to a gate (0). If an empty room cannot access any gate due to obstacles or layout constraints, it retains its INF value.

Examples

Example 1

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]]

Example 2

Input:

rooms = [[-1]]

Output:

[[-1]]

Constraints

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

Approach and Intuition

The premise revolves around updating the distance from each empty room (INF) to the nearest gate (0). Here are the structured steps to tackle the problem, amalgamating the intuition pulled from the given examples:

1. Initialization:

   • Start with identifying all gate locations in the grid and use them as starting points for breadth-first search (BFS). This efficient graph traversal technique helps to explore all neighbors level by level, ensuring the shortest path is always considered first.

2. Setting Up BFS:

   • Utilize a queue to manage cells as they are processed.
   • Enqueue all the gates at the beginning since they serve as the initial wavefronts from which distances are propagated.

3. Propagation:

   • Iteratively dequeue from the queue and for each cell, check its four possible neighbors (up, down, left, right).
   • If a neighbor is an empty room (INF), update its value to current cell's value + 1 (since it's one step away from the current cell), and enqueue it for subsequent processing.
   • Ensure not to cross boundaries of the grid or pass through walls (-1).

4. Edge Cases Handling:

   • If the room layout has only walls or isolated sections not accessible from any gates, the BFS will naturally maintain their INF values, adhering to the problem's requirements.

5. Efficiency Consideration:

   • Since each cell is processed at most once and enqueued/dequeued once, the approach operates in O(m * n) time complexity, making it efficient given the problem constraints.

This methodical exploration allows us to effectively fill each empty room with the minimum distance to a gate, grounded in the manner demonstrated by the examples wherein every step actively reduces the distance until the nearest gate is entrenched in each eligible cell.

Solutions

private static final int UNFILLED = Integer.MAX_VALUE;
private static final int OPEN_GATE = 0;
private static final List<int[]> MOVES = Arrays.asList(
        new int[] { 1,  0},
        new int[] {-1,  0},
        new int[] { 0,  1},
        new int[] { 0, -1}
);

public void fillRooms(int[][] rooms) {
    int rows = rooms.length;
    if (rows == 0) return;
    int cols = rooms[0].length;
    Queue<int[]> queue = new LinkedList<>();
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (rooms[i][j] == OPEN_GATE) {
                queue.add(new int[] { i, j });
            }
        }
    }
    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int currentRow = current[0];
        int currentCol = current[1];
        for (int[] move : MOVES) {
            int nextRow = currentRow + move[0];
            int nextCol = currentCol + move[1];
            if (nextRow < 0 || nextCol < 0 || nextRow >= rows || nextCol >= cols || rooms[nextRow][nextCol] != UNFILLED) {
                continue;
            }
            rooms[nextRow][nextCol] = rooms[currentRow][currentCol] + 1;
            queue.add(new int[] { nextRow, nextCol });
        }
    }
}