Condense but more readable (in one scroll) java BFS


  • 0
    C

    There a lot of good solutions in the forum but I haven't seen any "one-scroll" solution (I know I cheated by condensing the lines), so I just want to share mine. Hope this help. The comments near the code should help explain the solution.

    public class Solution {
        public void solve(char[][] board) {
            int row = board.length; if (row<3) return;    // there will be no capture if row or column is > 3!
            int col = board[0].length; if (col<3) return;
            int r1=0; int r2=row-1; int c1=0; int c2= col-1;  // r1, c1 are beginning index; r2 and c2 are end index;
            Queue<Integer> q = new LinkedList();              // Use a queue to store all the boarder "O" piece positions
    
            for (int i=c1; i<=c2; i++){                       // Go though the 4 boarders 
                if (board[r1][i]=='O'){ board[r1][i]='B'; q.add(r1*col+i);}  // top row  (save memory by using Modulus to store two numbers in one)
                if (board[r2][i]=='O'){ board[r2][i]='B'; q.add(r2*col+i);}  // bottom row
            }
            for (int i=r1; i<=r2; i++){
                if (board[i][c1]=='O'){ board[i][c1]='B'; q.add(i*col+c1);}  // leftmost column
                if (board[i][c2]=='O'){ board[i][c2]='B'; q.add(i*col+c2);}  // rightmost column
            }
    
            while (!q.isEmpty()){           // for all the stored position do a BFS to get all the connected pieces to flip
                int num = q.poll();         // note that boarder piece are being checked also, but it's ok becoz they have been fliped to 'B'
                int r = num/col; int c = num%col;
                if (r+1<r2 && board[r+1][c]=='O'){ board[r+1][c]='B'; q.add((r+1)*col+c);}
                if (r-1>r1 && board[r-1][c]=='O'){ board[r-1][c]='B'; q.add((r-1)*col+c);}
                if (c+1<c2 && board[r][c+1]=='O'){ board[r][c+1]='B'; q.add(r*col+c+1);}
                if (c-1>c1 && board[r][c-1]=='O'){ board[r][c-1]='B'; q.add(r*col+c-1);}
            }
    
            for (int i=0; i<row; i++)       // At last we just flip all the non capture (i.e. 'B') back to 'O', and all else will be 'X'
                for (int j=0; j<col; j++){
                    if (board[i][j]=='B') board[i][j]='O';
                    else board[i][j]='X';
                }
        }
    }

Log in to reply
 

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