Surrounded Regions

Problem

You are given an m x n board of characters 'X' and 'O'. A group of 'O' cells that are connected orthogonally is captured if it does not touch the border of the board anywhere, meaning it is completely enclosed by 'X'. Capture every such group by flipping all of its cells to 'X', in place. Groups that include at least one border cell are left unchanged.

• The board has at least one cell and at most 300 rows and 300 columns.
• Cells are only 'X' or 'O'.
• Modify the board in place; return nothing.

Examples

• Board

  X X X X X
  X O X O O
  X O X X X
  X X O O X
  X X X X X

  becomes

  X X X X X
  X X X O O
  X X X X X
  X X X X X
  X X X X X

  The vertical pair in column 1 and the horizontal pair in row 3 are enclosed and flip. The pair at (1,3),(1,4) survives because (1,4) lies on the right edge.
• [["O","X","X"],["X","O","X"],["X","X","O"]] becomes [["O","X","X"],["X","X","X"],["X","X","O"]]. The centre O only touches the corner Os diagonally, which does not count, so it is captured while the corners stay.
• [["O","O","O"],["O","X","O"],["O","O","O"]] is unchanged: every O is on the border.

Hints

1. Instead of asking "is this region enclosed?", ask "which O cells can not be captured?"
2. Every uncapturable O is connected to a border O. Start from the border.
3. Flood fill from every border O, temporarily marking reached cells safe. Then rewrite the board: safe cells become O, all other Os become X.