My answer, BFS - easy to understand


  • 2
    M
     private static class Coordinate {
        int row;
        int col;
        public Coordinate(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
    // Standard BFS solution
    public void wallsAndGates(int[][] rooms) {
        if (rooms == null || rooms.length == 0 || rooms[0].length == 0) return;
        boolean visited[][] = new boolean[rooms.length][rooms[0].length];
        Queue<Coordinate> explores = new LinkedList<>();
        for (int row = 0 ; row < rooms.length ; row++) {
            for (int col = 0 ; col < rooms[0].length ; col++) {
                if (rooms[row][col] == 0) {
                    explores.offer(new Coordinate(row,col));
                    visited[row][col] = true;
                }
            }
        }
        int currentDistance = 0;
        int thisLevelChildNum = explores.size();
        int nextLevelChildNum = 0;
        while (!explores.isEmpty()) {
            Coordinate current = explores.poll();
            thisLevelChildNum--;
            if (rooms[current.row][current.col] > 0) rooms[current.row][current.col] = currentDistance;
            // Not out of bound and Not visited and Not Wall -> Child
            // Mark the child visited when it joins the queue. Since 2 children can be at the same level, and the first processed child put the second one into the queue again!
            if (current.row >= 1 && !visited[current.row - 1][current.col] && rooms[current.row - 1][current.col] > 0) {
                explores.offer(new Coordinate(current.row - 1, current.col));
                visited[current.row - 1][current.col] = true;
                nextLevelChildNum++;
            }
            if (current.row < rooms.length - 1 && !visited[current.row + 1][current.col] && rooms[current.row + 1][current.col] > 0) {
                explores.offer(new Coordinate(current.row + 1, current.col));
                visited[current.row + 1][current.col] = true;
                nextLevelChildNum++;
            } 
            if (current.col >= 1 && !visited[current.row][current.col - 1] && rooms[current.row][current.col - 1] > 0) {
                explores.offer(new Coordinate(current.row, current.col - 1));
                visited[current.row][current.col - 1] = true;
                nextLevelChildNum++;
            }
            if (current.col < rooms[0].length - 1  && !visited[current.row][current.col + 1] && rooms[current.row][current.col + 1] > 0) {
                explores.offer(new Coordinate(current.row, current.col + 1));
                visited[current.row][current.col + 1] = true;
                nextLevelChildNum++;
            }
            if (thisLevelChildNum == 0) {
                thisLevelChildNum = nextLevelChildNum;
                nextLevelChildNum = 0;
                currentDistance++;
            }
        }
    }

  • 0
    C

    Awesome! I feel that BFS should make more sense than DFS in this question. What about running time of this algorithm?


Log in to reply
 

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