WallsAndGatesOptimal.java

public class Solution {
    class Node{
        int x, y; 
        int d; 
        Node(int x, int y, int d) {
            this.x = x; 
            this.y = y; 
            this.d = d; 
        }
    }
    
    private int[][] dirs = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; 
    
    private int INF = 2147483647;
    
    /**
     * @param rooms: m x n 2D grid
     * @return: nothing
     */
    public void wallsAndGates(int[][] rooms) {
        int m = rooms.length; 
        int n = rooms[0].length; 
        Queue<Node> q = new LinkedList<>(); 
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (rooms[i][j] == 0) {
                    q.add(new Node(i, j, 0));
                }
            }
        }
        
        while (!q.isEmpty()) {
            Node front = q.remove();
            
            for (int[] dir : dirs) {
                int x = front.x + dir[0]; 
                int y = front.y + dir[1]; 
                if (x < 0 || x >= m || y < 0 || y >= n || rooms[x][y] != INF) continue;
                rooms[x][y] = front.d + 1; 
                Node node = new Node(x, y, front.d + 1);
                q.add(node);
            }
        }
    }
}