130 Surrounded Regions

130. Surrounded Regions

1. Question

Given a 2D board containing'X'and'O'(the letter O), capture all regions surrounded by'X'.

A region is captured by flipping all'O's into'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

2. Implementation

(1) BFS

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) {
            return;
        }

        int m = board.length, n = board[0].length;
        int[][] directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

        for (int i = 0; i < m; i++) {
            fill(board, i, 0, directions);
            fill(board, i, n - 1, directions);
        }

        for (int j = 0; j < n; j++) {
            fill(board, 0, j, directions);
            fill(board, m - 1, j, directions);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
                else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void fill(char[][] board, int row, int col, int[][] directions) {
        if (board[row][col] == 'O') {
            board[row][col] = '#';
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[] {row, col});

            while (!queue.isEmpty()) {
                int[] cell = queue.remove();
                int curRow = cell[0], curCol = cell[1];

                for (int[] direction : directions) {
                    int nextRow = curRow + direction[0];
                    int nextCol = curCol + direction[1];

                    if (isValid(board, nextRow, nextCol)) {
                        board[nextRow][nextCol] = '#';
                        queue.add(new int[] {nextRow, nextCol});
                    }
                }
            }
        }
    }

    public boolean isValid(char[][] board, int row, int col) {
        return row >= 0 && row < board.length && col >= 0 && col < board[0].length && board[row][col] == 'O';
    }
}

3. Time & Space Complexity

BFS: 时间复杂度O(mn), 空间复杂度O(mn), m和n分别为board的行数和列数