130. Surrounded Regions

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

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

Example 1:

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.

My Solutions:

方法1：DFS

只有在边界上的‘O’是肯定不会被X包围的，因此从边界上的所有 ‘O’ 着手，以他们为起点做dfs，找到所有与他们连通的 ‘O’ ，并将他们替换为其他字符比如 ‘A’。这样操作完所有格子后，没有被改变过的 ‘O’ 一定是被 ‘X’ 包围的所以无法被改变。

最后再遍历一遍矩阵上每一个点，遇到 ‘O’ 时替换为 ‘X’，遇到 ‘A’时还原为 ‘O’ 。

public void solve(char[][] board) {
    
    int m = board.length, n = board[0].length;
    
    // 对每一行，遍历在column左右边界上的‘O’
    for (int i = 0; i < m; i++) {
        if (board[i][0] == 'O') dfs(board, i, 0);
        if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
    }

    // 对每一列，遍历在row上下边界上的‘O’
    for (int i = 0; i < n; i++) {
        if (board[0][i] == 'O') dfs(board, 0, i);
        if (board[m - 1][i] == 'O') dfs(board, m - 1, i);
    }

    // change 'O' to 'X' and restore 'A' to 'O'
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == 'A') board[i][j] = 'O';
        }
    }
}

private void dfs(char[][] board, int i, int j) {
    int m = board.length, n = board[0].length;
    // 注意这里是i>=m和j>=n，因为这两种情况是不允许的
    if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;

    board[i][j] = 'A';
    dfs(board, i + 1, j);
    dfs(board, i - 1, j);
    dfs(board, i, j + 1);
    dfs(board, i, j - 1);
}

方法2：BFS

DFS容易导致栈溢出，用BFS不会有这个问题。

public void solve(char[][] board) {
    int m = board.length, n = board[0].length;
    Queue<int[]> q = new LinkedList<>(); // 用来储存格子坐标

    // 遍历在column和row边界上的‘O’
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                if (board[i][j] == 'O') {
                    q.offer(new int[]{i, j}); // 把O的格子加入q
                    board[i][j] = 'A'; // O格子变成A
                }
            }
        }
    }

    int[] dx = new int[]{0, 0, -1, 1};
    int[] dy = new int[]{-1, 1, 0, 0};
    while (!q.isEmpty()) {
        int[] cell = q.poll();
        int row = cell[0], col = cell[1];
        // 遍历所有存下来的O格子的四个方向
        for (int i = 0; i < 4; i++) {
            int r = row + dx[i], c = col + dy[i];
            if (r < 0 || r >= m || c < 0 || c >= n || board[r][c] != 'O') continue;
            board[r][c] = 'A'; // 改变O格子为A
            q.offer(new int[]{r, c});
        }
    }

    // change 'O' to 'X' and restore 'A' to 'O'
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            else if (board[i][j] == 'A') board[i][j] = 'O';
        }
    }
}