День 22 — Стены и ворота

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

Это решается с помощью поиска в ширину (BFS). Сначала обратите внимание, где все ворота. Затем с помощью очереди входите в последующие комнаты и заменяете там значения расстоянием от ворот. Гарантируется, что значение в этой комнате будет наименьшим расстоянием от любых ворот, потому что мы обнаружили бы эту комнату раньше. Все другие встречи с этой комнатой из других ворот будут позже отключены (т.е. расстояние будет больше).

class Solution {
    public void wallsAndGates(int[][] rooms) {
        if(rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
        Queue<int[]> q = new LinkedList<>();
        int rows = rooms.length;
        int cols = rooms[0].length;
        for(int i = 0; i < rooms.length; i++){
            for(int j = 0; j < rooms[0].length; j++){
                if(rooms[i][j] == 0) q.offer(new int[]{i,j});
            }
        }
        
        while(!q.isEmpty()) {
            int[] qData = q.poll();
            int r = qData[0];
            int c = qData[1];
            int newVal = rooms[r][c]+1;
            // check in all 4 directions: up down left right
            if (r > 0 && rooms[r-1][c] == Integer.MAX_VALUE) {
                rooms[r-1][c] = newVal;
                q.offer(new int[]{(r-1),c});
            }
            if (r < rows-1 && rooms[r+1][c] == Integer.MAX_VALUE) {
                rooms[r+1][c] = newVal;
                q.offer(new int[]{(r+1),c});
            }
            if (c > 0 && rooms[r][c-1] == Integer.MAX_VALUE) {
                rooms[r][c-1] = newVal;
                q.offer(new int[]{r,c-1});
            }
            if (c < cols-1 && rooms[r][c+1] == Integer.MAX_VALUE) {
                rooms[r][c+1] = newVal;
                q.offer(new int[]{r,c+1});
            }
        }
    }
}