Surrounded Regions

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'. A region is captured by flipping all 'O's that are not connected to the border to 'X'.

Function signature

func Solve(board [][]byte)

Inputs / outputs

• board: grid of 'X' and 'O'.
• Return: nothing; mutate board in-place.

Example

Input:
X X X X
X O O X
X X O X
X O X X

Output:
X X X X
X X X X
X X X X
X O X X

Constraints

• 1 <= rows, cols <= 200

Core idea (near-solution)

Only 'O' cells connected to the border survive. Mark all border-connected 'O' cells as safe, then flip the rest.

Invariant: after BFS from borders, every safe 'O' is marked and should not be flipped.

Algorithm (step-by-step)

1. For every border cell that is 'O', BFS/DFS and mark all reachable 'O' as safe (e.g., 'S').
2. Scan the board:
   • Flip remaining 'O' to 'X'.
   • Flip 'S' back to 'O'.

Correctness sketch

• Invariant: after BFS from borders, every safe 'O' is marked and should not be flipped.
• DFS visits exactly all nodes reachable from a start node.
• Marking visited prevents revisits and guarantees termination.
• Repeating from unvisited nodes correctly handles all components.

Trace (hand walkthrough)

Example input:
Input:
X X X X
X O O X
X X O X
X O X X

Output:
X X X X
X X X X
X X X X
X O X X

Walk:
- border O at (3,1) marked safe
- all other O are not border-connected -> flip to X
- restore safe O at (3,1) -> final grid shown

Pitfalls to avoid

• Flipping border-connected 'O' cells to 'X'.
• Forgetting to restore temporary marks after the flood fill.

Complexity

• Time: O(r*c)
• Extra space: O(r*c) worst-case for the queue.

Implementation notes (Go)

• Mark border-connected 'O' as a temporary value (e.g., '#').
• After flood fill, flip remaining 'O' to 'X' and restore '#'.