Surrounded Regions (standard question)

For Surrounded Regions, an O should remain only when it is connected to the board boundary through O cells. Traverse from every border cell containing O, using DFS or BFS, and temporarily mark every reachable O as safe, for example S. Do this before flipping anything, because a boundary-connected component can extend far into the board. Then scan all cells: change unmarked O to X because those are enclosed, and change S back to O. With an m x n board, each cell is visited a constant number of times, so time is O(mn) and auxiliary traversal space is O(mn) in the worst case; iterative BFS avoids recursion-depth risk. Check one-row or one-column boards, all X, and all O. The correctness argument is a partition: every O is either boundary-reachable and protected, or not boundary-reachable and therefore enclosed.