My java solution, not very concise but the idea is clear


  • 0
    T

    for each 'O' cell , try to see if the expanded area "borders on " the 4 sides, if so, recursively fills that patch with X. originally I coded the recursive "border check" and the "recursive fill" using plain recursion, but then got stack overflow for large instances. then I had to change the implementation to a stack. a queue would work similarly.

    another post provides a better approach and directly tries to flip from the "O" cells on the border, so there is no "bordering check" anymore, 1 step finishes the job.

    public class Solution {
    int m;
    int n;
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
         m = board.length;
         if (board[0] == null) return;
         n = board[0].length;
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if ( (board[i][j] == 'O' ) )
                	if (recursiveBordering(board, i, j))
                    recursiveFlip(board, i,j, '2');
                	else
                	recursiveFlip(board, i,j, 'X');
            }
        }
        
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if (board[i][j] == '2')
                    board[i][j] = 'O';
        
    }
    
    boolean recursiveBordering(char[][]board, int i0, int j0) {
        Stack<int[]> q = new Stack<int[]>();
        q.push(new int[]{i0,j0});
        while(!q.empty()) {
            
        int []ij = q.pop();
        int i = ij[0];
        int j = ij[1];
        boolean bordering = (i == 0 || i==m-1 || j==0 || j== n-1 ) && (board[i][j] == 'O' || board[i][j] == '1');
    
        if (bordering) return true;
        
        board[i][j] = '1';
        if ( i<m-1 && board[i+1][j] == 'O')
            q.push(new int[]{i+1,j});
        
        if (i>0  && board[i-1][j] == 'O')
            q.push(new int[]{i-1,j});
            
        if (j<n-1 && board[i][j+1] == 'O')
           q.push(new int[]{i,j+1});
        if (j>0 && board[i][j-1] == 'O')
           q.push(new int[]{ i,j-1});
        
        
        }
        return false;
        
    }
    
    void recursiveFlip(char [][]board, int i0, int j0, char c) {
                Stack<int[]> q = new Stack<int[]>();
        q.push(new int[]{i0,j0});
        while(!q.empty()) {
            
        int []ij = q.pop();
        int i = ij[0];
        int j = ij[1];
        board[i][j] = c;
        
        if (i <m-1 && ( board[i+1][j] == 'O' || board[i+1][j] == '1'))
            q.push(new int[]{ i+1, j});
           if (i >0 && ( board[i-1][j] == 'O' || board[i-1][j] == '1'))
            q.push(new int[]{ i-1, j});
           if (j <n-1 && ( board[i][j+1] == 'O' || board[i][j+1] == '1'))
            q.push(new int[]{i, j+1});
           if (j >0 && ( board[i][j-1] == 'O' || board[i][j-1] == '1'))
            q.push(new int[]{ i, j-1});
    
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.