Capture Surrounded Regions

Imagine a 2D board game where 'X' represents a captured piece and 'O' represents an open space. Your task is to flip all 'O's that are completely surrounded by 'X's into 'X's. However, there's a crucial exception: any 'O' that is connected to an 'O' on the border of the board should not be flipped. This problem is akin to flood-fill algorithms and is a common exercise in graph traversal.

Problem Description

Given an m x n 2D board where each cell is either 'X' or 'O', modify the board such that every 'O' that is not connected to an 'O' on the border (either directly or indirectly through other 'O's) is transformed into an 'X'. An 'O' is considered connected to the border if it is on the border itself or if it is adjacent (up, down, left, or right) to another 'O' that is connected to the border.

Key Requirements:

• Modify the board in-place.
• Only 'O's that are completely enclosed by 'X's should be flipped.
• 'O's that can reach the border (directly or indirectly) should remain as 'O's.

Expected Behavior:

The function should take the 2D board as input and return the modified board.

Edge Cases:

• An empty board.
• A board with only 'X's or only 'O's.
• A board where all 'O's are connected to the border.
• A board where no 'O's are connected to the border.

Examples

Example 1:

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"]
]

Explanation:
The 'O's at (1,1), (1,2), and (2,2) are all surrounded by 'X's and are not connected to any 'O' on the border.
The 'O' at (3,1) is on the border, so it remains an 'O'.

Example 2:

Input:
[
  ["X"]
]

Output:
[
  ["X"]
]

Explanation:
No 'O's to flip.

Example 3:

Input:
[
  ["O","O","O"],
  ["O","O","O"],
  ["O","O","O"]
]

Output:
[
  ["O","O","O"],
  ["O","O","O"],
  ["O","O","O"]
]

Explanation:
All 'O's are connected to the border.

Constraints

• m == board.length
• n == board[i].length
• 1 <= m, n <= 200
• board[i][j] is either 'X' or 'O'.
• The solution should aim for a time complexity better than O(mn * mn), ideally O(m*n).

Notes

Consider how you can efficiently identify 'O's that are not connected to the border. A common approach involves starting from the border and marking reachable 'O's. Any 'O's that remain unmarked after this process are the ones that should be flipped. Think about graph traversal algorithms like Depth-First Search (DFS) or Breadth-First Search (BFS).