Surrounded Regions | Leetcode

Given a 2D board containing 'X' and '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: Iterate through all non-edge cells in the board in any order. For each O, perform BFS to obtain all reachable O's. If the BFS did not find a way to the edge of the board, then mark all BFS-reachable cells as X.

public class Solution {

    private final Set<Integer> seenOs = new HashSet<>();
    private final Set<Integer> bfsSeenOs = new HashSet<>();
    private final LinkedList<Integer> bfsQueue = new LinkedList<>();
    private int height;
    private int width;
    private boolean foundWayOut;
        
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
        
        height = board.length;
        width = board[0].length;
        
        // No need to go through the cells at the board edges since we will never
        // convert them to X's.
        for (int y = height - 2; y >= 1; y--) {
            for (int x = width - 2; x >= 1; x--) {
             // If this is an X, ignore it since we cannot do anything with it.
                if (board[y][x] == 'X') continue;
                
                // Calculate the number this cell represents.
                int n = (y * width) + x;
                
                // If we have already visited this O, then skip it.
                if (seenOs.contains(n)) continue;

                // Perform BFS starting from current cell.
                bfsSeenOs.add(n);                
                bfsQueue.add(n);
                foundWayOut = false;
                
                do {
                    int bfsN = bfsQueue.removeFirst();
                    int bfsY = bfsN / width;
                    int bfsX = bfsN % width;

                    // Check each neighbor to see if we should add it to the BFS queue.
                    if (bfsY > 0)          bfsCheckAddNeighbor(board, bfsY - 1, bfsX);
                    if (bfsY < height - 1) bfsCheckAddNeighbor(board, bfsY + 1, bfsX);
                    if (bfsX > 0)          bfsCheckAddNeighbor(board, bfsY, bfsX - 1);
                    if (bfsX < width - 1)  bfsCheckAddNeighbor(board, bfsY, bfsX + 1);
                    
                } while (!bfsQueue.isEmpty());

                // Mark all current BFS-reachable nodes as seen.
                seenOs.addAll(bfsSeenOs);
                
                // If we did not find a way out, then change all reachable O's to X's.
                if (!foundWayOut) {
                    for (int m: bfsSeenOs) {
                        board[m / width][m % width] = 'X';
                    }
                }

                bfsSeenOs.clear();
            }
        }
    }
    
    private void bfsCheckAddNeighbor(char[][] board, int y, int x) {
     // Skip all X's.
        if (board[y][x] == 'X') return;
        
        int n = (y * width) + x;
        
        // If we have already visited this cell in this BFS, skip it.
        if (bfsSeenOs.contains(n)) return;

        // These two collections are very similar, but are used differently.
        // The set is for quick add/get. The queue is for linear iteration.
        bfsSeenOs.add(n);
        bfsQueue.add(n);
        
        // If this cell is at the edge of the board, then we have found a way out!
        if (y == 0 || y == height - 1 || x == 0 || x == width - 1) {
            foundWayOut = true;
        }
    }

}