My java solution, very easy to understand


  • 0
    T

    the straight-forward recursive call causes stack overflow, so had to translate to a BFS approach

    public class Solution {
        int m;
        int n;
        public void solve(char[][] board) {
            
         m = board.length;
         if (m == 0) return;
         n = board[0].length;
         if (n == 0 ) return ;
         for(int i=0;i<m;i++)
            for(int j=0;j<n;j++) {
                if (board[i][j] == 'O' ) {
                    if (recursiveFlip(board, i,j, 'O', '1'))
                        recursiveFlip(board,i,j, '1', 'X');
                }
            }
            
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++) {
                if (board[i][j] == '1' ) {
                        recursiveFlip(board,i,j, '1', 'O');
                }
            }
        }
        Queue<int[]> q = new LinkedList<int[]>();
        
        // if the enclosed area starting from [i,j] does not touch on border,
        // return true
        boolean recursiveFlip(char[][]board, int i, int j, char from, char to) {
            boolean result = true;
            q.add(new int[]{i,j});
            while(q.size()>0) {
                int[] coord = q.remove();
                i = coord[0]; j = coord[1];
                if ((i ==m || i<0 || j==n || j<0)) {
                    result = false;
                    continue;
                }
                if (board[i][j] != from) continue;
                board[i][j] = to;
                q.add(new int[]{i-1,j});
                q.add(new int[]{i+1,j});
                q.add(new int[]{i,j+1});
                q.add(new int[]{i,j-1});
    
            }
            
            return result;
        }
    }

Log in to reply
 

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