Surrounded Regions leetcode

Given a 2D board containing 'X' and '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

这道题的题意是把那些四周被'X'包围的'O'都变成'X'

那么可以发现最外面的四周如果有O, 那么与之相连的O才能不被包围

所以就对最外层的'O'进行特殊处理, 对外层的'O'进行BFS, 把与之相连的O和它本身都变成'#'

这样一来对于整个矩阵 如果还是'O'的说明他被X包围, 应该变成X, 把所有的# 再变成O

//bfs
public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length <= 1 || board[0].length <= 1) {
            return;
        }
        for (int i = 0; i <board[0].length; i++) {//fill第一行和最后一行
            fill(board, 0, i);
            fill(board, board.length - 1, i);
        }
        for (int i = 0; i < board.length; i++) {//对第一列和最后一列fill
            fill(board, i, 0);
            fill(board, i, board[0].length - 1);
        }
        for (int i = 0; i< board.length; i++) {
            //最后一次遍历, 把内部的'O'变成'X', '#'变成'O'
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    public void fill (char[][] board, int i, int j) {
        if (board[i][j] != 'O') {
            return;
        }
        board[i][j] = '#';
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(i * board[0].length + j);//把矩阵的横纵坐标编码存储
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            //解码
            int row = cur / board[0].length;
            int column = cur % board[0].length;
            if (row > 0 && board[row - 1][column] == 'O') {//向上找
                queue.offer((row - 1) * board[0].length + column);
                board[row - 1][column] = '#';
            }
            if (row < board.length - 1 && board[row + 1][column] == 'O') {//向下找
                queue.offer((row + 1) * board[0].length + column);
                board[row + 1][column] = '#';
            }
            if (column > 0 && board[row][column - 1] == 'O') {//向左找
                queue.offer(row * board[0].length + column - 1);
                board[row][column - 1] = '#';
            }
            if (column < board[0].length - 1 && board[row][column + 1] == 'O') {//向右找
                queue.offer(row * board[0].length + column + 1);
                board[row][column + 1] = '#';
            }
        }
    }
}
//dfs cause stack over flow
public class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length <= 1 || board[0].length <= 1) {
            return;
        }
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                bfs(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                bfs(board, i, n - 1);
            }
        }
        for (int i = 1; i <= n - 2; i++) {
            if (board[0][i] == 'O') {
                bfs(board, 0, i);
            }
            if (board[m-1][0] == 'O') {
                bfs(board, m - 1, i);
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    public void bfs(char[][] board, int column, int row) {
        if (column < 0 || column >= board.length || row < 0 || row >= board[0].length || board[column][row] != 'O') {
            return;
        }
        board[column][row] = '#';
        bfs(board, column - 1, row);
        bfs(board, column + 1, row);
        bfs(board, column, row - 1);
        bfs(board, column, row + 1);
    }
}