Simple BFS in Java


  • 0
    N

    Regular BFS.

    static int row[] = {-1,0,0,1};
        static int col[] = {0,-1,1,0};
        
        boolean isValid(int i, int j, int[][] rooms) {
            return (i < rooms.length && j < rooms[0].length && i>=0 && j>=0 && rooms[i][j] == Integer.MAX_VALUE);
        }
        
        public void wallsAndGates(int[][] rooms) {
            if (rooms.length == 0) return;
            Queue q = new LinkedList();
            for (int i = 0; i < rooms.length; i++)
                for (int j = 0; j < rooms[0].length; j++)
                    if (rooms[i][j] == 0)
                        q.add(new int[]{i,j});
            
            while(!q.isEmpty()) {
                int[] pair = (int[])q.remove();
                int r = pair[0], c = pair[1];
                for (int d = 0; d < 4; d++) {
                    int x=r+row[d], y=c+col[d];
                    if (isValid(x,y,rooms)) {
                        rooms[x][y] = rooms[r][c]+1;
                        q.add(new int[]{x,y});
                    }
                }
            }
            return;
        }
    

Log in to reply
 

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