Skip to content

286. 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 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

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.

Example 1:

img

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.

Solution:

class Solution {
    static class Node{
        int row;
        int col; 
        int distance;

        Node(int row, int col, int distance){
            this.row = row;
            this.col = col; 
            this.distance = distance;
        }
    }
    public void wallsAndGates(int[][] rooms) {
        Queue<Node> queue = new LinkedList<>();


        for (int i = 0; i < rooms.length; i++){
            for (int j = 0; j < rooms[0].length; j++){
                if (rooms[i][j] == 0){
                    queue.add(new Node(i, j, 0));
                }
            }
        }

        while(!queue.isEmpty()){
            Node cur = queue.poll();
            helper(cur.row - 1, cur.col, cur.distance, rooms, queue);
            helper(cur.row, cur.col - 1, cur.distance, rooms, queue);
            helper(cur.row + 1, cur.col, cur.distance, rooms, queue);
            helper(cur.row, cur.col + 1, cur.distance, rooms, queue);
        }
    }

    private void helper(int row, int col, int distance, int[][] rooms, Queue<Node> queue){
        if (row < 0 || row >= rooms.length || col < 0 || col >= rooms[0].length || rooms[row][col] != 2147483647){
            return;
        }

        if (rooms[row][col] > distance + 1){
            rooms[row][col] = distance + 1;
            queue.add(new Node(row, col, distance + 1));
        }
    }
}

// TC: O(n^2)
// SC: O(n^2)