LeetCode 130. Surrounded Regions - (Problem Link - https://leetcode.com/problems/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 fu…

SurroundedRegions.java

/**
LeetCode 130. 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
*/

public class SurroundedRegions {
    static class Pair{
        int row;
        int col;
        Pair(int x, int y){
            row = x;
            col = y;
        }
    }
    public void solve(char[][] board) {
        /**
        * APPROACH:
        * Only way for a 'O' to not be surrounded is by being on the boundary of the board. We will run BFS from all 'O's 
        * on the boundary to mark other reachable 'O's.
        * In the end, the only 'O's which have not been marked are the ones surrounded by 'X's. We will convert those 
        * unmarked 'O's to 'X's.
        */
        if(board.length == 0) return;
        boolean[][] escapeRoutes = new boolean[board.length][board[0].length];
        Deque<Pair> q = new ArrayDeque<Pair>();
        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};
        // Capture 'O' from first and last row
        for(int i = 0; i < board[0].length; i++){
            if(board[0][i] == 'O'){
                q.add(new Pair(0, i));
            }
            if(board[board.length - 1][i] == 'O'){
                q.add(new Pair(board.length - 1, i));
            }
        }
        // Capture 'O' from first and last column
        for(int j = 1; j < board.length - 1; j++){
            if(board[j][0] == 'O'){
                q.add(new Pair(j, 0));
            }
            if(board[j][board[0].length - 1] == 'O'){
                q.add(new Pair(j, board[0].length - 1));
            }
        }
        // Run a BFS search
        while(!q.isEmpty()){
            Pair current = q.remove();
            escapeRoutes[current.row][current.col] = true;
            for(int k = 0; k < 4; k++){
                int newRow = current.row + dx[k];
                int newCol = current.col + dy[k];
                if(newRow >= 0 && newRow <= board.length - 1 &&
                newCol >= 0 && newCol <= board[0].length - 1){
                    if(board[newRow][newCol] == 'O' && !escapeRoutes[newRow][newCol]){
                        q.add(new Pair(newRow, newCol));
                        escapeRoutes[newRow][newCol] = true;
                    }
                }
            }
        }
        // Convert unmarked 'O's to 'X's
        for(int m = 0; m < board.length; m++){
            for(int n = 0; n < board[0].length; n++){
                if(board[m][n] == 'O' && !escapeRoutes[m][n]){
                    board[m][n] = 'X';
                }
            }
        }
    }
}