Surrounded Regions

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

Solution 1: DFS, Line 29: java.lang.StackOverflowError

public class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        if(m==0) return;
        int n = board[0].length;
        
        for(int c=0; c<n; c++) {
            if(board[0][c]=='O') spread(board,0,c);
            if(board[m-1][c]=='O') spread(board,m-1,c);
        }
        for(int r=1; r<m-1; r++) {
            if(board[r][0]=='O') spread(board,r,0);
            if(board[r][n-1]=='O') spread(board,r,n-1);
        }
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
            	if(board[i][j]=='O') board[i][j]='X';
                if(board[i][j]=='A') board[i][j]='O';
            }
        }
    }
    public void spread(char[][] board, int i, int j){
        int m = board.length;
        int n = board[0].length;
        board[i][j] = 'A';
        if(i>0 && board[i-1][j]=='O') spread(board,i-1,j);
        if(i<m-1 && board[i+1][j]=='O') spread(board,i+1,j);
        if(j>0 && board[i][j-1]=='O') spread(board,i,j-1);
        if(j<n-1 && board[i][j+1]=='O') spread(board,i,j+1);
    }
}

Solution 2: BFS

public class Solution {
    public void solve(char[][] board) {
        int m = board.length;
        if(m==0) return;
        int n = board[0].length;
        
        for(int c=0; c<n; c++) {
            if(board[0][c]=='O') spread(board,0,c);
            if(board[m-1][c]=='O') spread(board,m-1,c);
        }
        for(int r=1; r<m-1; r++) {
            if(board[r][0]=='O') spread(board,r,0);
            if(board[r][n-1]=='O') spread(board,r,n-1);
        }
        
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(board[i][j]=='O') board[i][j]='X';
                if(board[i][j]=='A') board[i][j]='O';
            }
        }
    }
    public void spread(char[][] board, int x, int y){
        int m = board.length;
        int n = board[0].length;
        board[x][y] = 'A';
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        while(!q.isEmpty()){
            int[] point = q.poll();
            int i = point[0];
            int j = point[1];
            if(i>0 && board[i-1][j]=='O') {board[i-1][j] = 'A';q.add(new int[]{i-1,j});}
            if(i<m-1 && board[i+1][j]=='O') {board[i+1][j] = 'A';q.add(new int[]{i+1,j});}
            if(j>0 && board[i][j-1]=='O') {board[i][j-1] = 'A';q.add(new int[]{i,j-1});}
            if(j<n-1 && board[i][j+1]=='O') {board[i][j+1] = 'A';q.add(new int[]{i,j+1});}
        }
        
    }
}