BFS-based solution in Java


  • 5
    M
    /*
        dfs, bfs, union-find都可以做, 基本思路是
        从在四个边的各个'O'开始搜索, 连在一起的'O'就是不能被包围的, 其余的点都应该设为'X'.
        
        如果选择bfs, 可以把所有边上的所有'O'一起入队, 同时进行bfs
    */
    public class Solution {
        public void solve(char[][] board) {
            if (board == null || board.length == 0 || board[0].length == 0) return;
            int height = board.length, width = board[0].length;
            Deque<int[]> queue = new ArrayDeque<>();  // int[2] as [row, col]
            for (int i = 0; i < width; ++i) {
                if (board[0][i] == 'O') {
                    queue.addLast(new int[] {0, i});
                    board[0][i] = 'V';  // mark as visited
                }
                if (board[height - 1][i] == 'O') {
                    queue.addLast(new int[] {height - 1, i});
                    board[height - 1][i] = 'V';
                }
            }
            for (int i = 1; i < height - 1; ++i) {
                if (board[i][0] == 'O') {
                    queue.addLast(new int[] {i, 0});
                    board[i][0] = 'V';
                }
                if (board[i][width - 1] == 'O') {
                    queue.addLast(new int[] {i, width - 1});
                    board[i][width - 1] = 'V';
                }
            }
            while (!queue.isEmpty()) {
                int[] cur = queue.removeFirst();
                if (cur[0] - 1 >= 0 && board[cur[0] - 1][cur[1]] == 'O') {  // up
                    queue.addLast(new int[] {cur[0] - 1, cur[1]});
                    board[cur[0] - 1][cur[1]] = 'V';
                }
                if (cur[0] + 1 < height && board[cur[0] + 1][cur[1]] == 'O') {  // down
                    queue.addLast(new int[] {cur[0] + 1, cur[1]});
                    board[cur[0] + 1][cur[1]] = 'V';
                }
                if (cur[1] - 1 >= 0 && board[cur[0]][cur[1] - 1] == 'O') {  // left
                    queue.addLast(new int[] {cur[0], cur[1] - 1});
                    board[cur[0]][cur[1] - 1] = 'V';
                }
                if (cur[1] + 1 < width && board[cur[0]][cur[1] + 1] == 'O') {  // right
                    queue.addLast(new int[] {cur[0], cur[1] + 1});
                    board[cur[0]][cur[1] + 1] = 'V';
                }
            }
            for (int i = 0; i < height; ++i) {
                for (int j = 0; j < width; ++j) {
                    if (board[i][j] == 'O') board[i][j] = 'X';
                    else if (board[i][j] == 'V') board[i][j] = 'O';
                }
            }
        }
    }

Log in to reply
 

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