JAVA BFS Solution


  • 0
    L
    public class Solution {
        public void wallsAndGates(int[][] rooms) {
            if (rooms.length == 0 || rooms[0].length == 0) return;
            Queue<int[]> queue = new LinkedList<>();
            int dis = 1;
            for (int i = 0; i < rooms.length; i++) {
                for (int j = 0; j < rooms[0].length; j++) {
                    if (rooms[i][j] == 0) {
                        queue.offer(new int[] {i, j});
                    }
                }
            }
            int[] x = {0, 0, -1, 1};
            int[] y = {-1, 1, 0, 0};
            while(!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; i++) {
                    int[] p = queue.poll();
                    for (int k = 0; k < 4; k++) {
                        int a = p[0] + x[k];
                        int b = p[1] + y[k];
                        if (isValid(rooms, a, b, dis)) {
                            rooms[a][b] = dis;
                            queue.offer(new int[] {a, b});
                        }
                    }
                }
                dis++;
            }
        }
        private boolean isValid(int[][] rooms, int i, int j, int dis) {
            if (i < 0 || i > rooms.length - 1 || j < 0 || j > rooms[0].length - 1 || rooms[i][j] == -1 || rooms[i][j] < dis) return false;
            return true;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.