9ms Java BFS


  • 1
    T

    Do BFS on each boundary node that is 'O'. So visited nodes are not surrounded by 'X'. Then we only flip those 'O' nodes that are not visited.

    class Solution {
        private int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        public void solve(char[][] board) {
            if (board == null || board.length == 0 || board[0].length == 0) {
                return;
            }
            int m = board.length;
            int n = board[0].length;
            boolean[][] visited = new boolean[m][n];
            Deque<int[]> queue = new LinkedList<>();
            for (int j=0; j<n; j++) {
                if (board[0][j] == 'O') {
                    visited[0][j] = true;
                    queue.add(new int[]{0, j});
                }
                if (board[m-1][j] == 'O') {
                    visited[m-1][j] = true;
                    queue.add(new int[]{m-1, j});
                }
            }
            for (int i=1; i<m-1; i++) {
                if (board[i][0] == 'O') {
                    visited[i][0] = true;
                    queue.add(new int[]{i, 0});
                }
                if (board[i][n-1] == 'O') {
                    visited[i][n-1] = true;
                    queue.add(new int[]{i, n-1});
                }
            }
            while (!queue.isEmpty()) {
                int[] cell = queue.poll();
                int i = cell[0];
                int j = cell[1];
                for (int[] dir : dirs) {
                    int ni = i+dir[0];
                    int nj = j+dir[1];
                    if (ni>0 && ni<m && nj>0 && nj<n && board[ni][nj] == 'O' && !visited[ni][nj]) {
                        visited[ni][nj] = true;
                        queue.add(new int[]{ni, nj});
                    }
                }
            }
            for (int i=0; i<m; i++) {
                for (int j=0; j<n; j++) {
                    if (board[i][j] == 'O' && !visited[i][j]) {
                        board[i][j] = 'X';
                    }
                }
            }
        }
    }```

Log in to reply
 

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