0286. Walls and Gates

https://leetcode.com/problems/walls-and-gates

Description

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:

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

Example 3:

**Input:** rooms = [[2147483647]]
**Output:** [[2147483647]]

Example 4:

**Input:** rooms = [[0]]
**Output:** [[0]]

Constraints:

• m == rooms.length

• n == rooms[i].length

• 1 <= m, n <= 250

• rooms[i][j] is -1, 0, or 231 - 1.

ac1: BFS

class Solution {
    public void wallsAndGates(int[][] rooms) {
        // edge case
        if (rooms.length == 0 || rooms[0].length == 0) return;

        Queue<int[]> q = new LinkedList<int[]>();
        int row = rooms.length;
        int col = rooms[0].length;

        // walk, get gates
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (rooms[r][c] == 0) q.offer(new int[] {r, c});
            }
        }

        // BFS
        int layer = 0;
        while (!q.isEmpty()) {
            layer++;
            int len = q.size();
            for (int i = 0; i < len; i++) {
                int[] head = q.poll();
                int r = head[0]; int c = head[1];

                if (r < row-1 && rooms[r+1][c] > layer) {
                    rooms[r+1][c] = layer;
                    q.offer(new int[] {r+1, c});
                }
                if (r > 0 && rooms[r-1][c] > layer) {
                    rooms[r-1][c] = layer;
                    q.offer(new int[] {r-1, c});
                }    
                if (c < col-1 && rooms[r][c+1] > layer){
                    rooms[r][c+1] = layer;
                    q.offer(new int[] {r, c+1});
                } 
                if (c > 0 && rooms[r][c-1] > layer) {
                    rooms[r][c-1] = layer;
                    q.offer(new int[] {r, c-1});
                }
            }
        }
    }
}

/**
walk, get 0s
BFS, if val > layer, set val = layer, offer to queue
**/