LeetCode——被围绕的区域

NO.130 被围绕的区域中等

思路一：BFS 很典型的BFS，题目的重点在于处理边界一周的 ‘O’ 。

除了边界上的 ‘O’ 不会被替换为 ‘X’ ，和其接壤的 ‘O’ 也不会被替换，因为所有和 ‘O’ 接壤的 ‘O’ 都不算是被 ‘X’ 包围。

所以思路就是：遍历四周边界，将边界上的 ‘O’ 标记为 ‘‘ ，然后从这个 ‘\‘ 开展距离为1的广搜，搜索到接壤的 ‘O’ 也标记为 ‘*‘。当遍边界遍历完成，再次遍历整个 board ，将 ‘O’ 全部替换为 ‘X’ 、’*‘ 全部替换为 ‘O’ 。

int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int r, c;

public void solve(char[][] board) {
    if (board == null || board.length == 0) return;
    this.r = board.length;
    this.c = board[0].length;
    //第一列，最后一列
    for (int i = 0; i < r; i++) {
        if (board[i][0] == 'O') bfs(i, 0, board);
        if (board[i][c - 1] == 'O') bfs(i, c - 1, board);
    }
    //第一行、最后一行
    for (int j = 0; j < c; j++) {
        if (board[0][j] == 'O') bfs(0, j, board);
        if (board[r - 1][j] == 'O') bfs(r - 1, j, board);
    }
    //转换
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            board[i][j] = board[i][j] == '*' ? 'O' : 'X';
        }
    }
}

//广搜
private void bfs(int i, int j, char[][] board) {
    Queue<int[]> queue = new LinkedList<>();
    queue.add(new int[]{i, j});
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int k = 0; k < size; k++) {
            int[] poll = queue.poll();
            int x = poll[0];
            int y = poll[1];
            if (x >= 0 && x < r && y >= 0 && y < c && board[x][y] == 'O') {
                board[x][y] = '*';
                for (int[] dir : dirs) {
                    queue.offer(new int[]{x + dir[0], y + dir[1]});
                }
            }
        }
    }
}

时间复杂度：O(n)

空间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和源码:github

NO.130 被围绕的区域 中等

NO.130 被围绕的区域中等