Surrounded Regions - Medium Python Graphs Interview Problem

You are given an m x n matrix board containing 'X' and 'O' characters.

Capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that region.

A region is not captured if any 'O' in it touches the border of the board. Those border-connected 'O's and any 'O's connected to them remain 'O'.

The function modifies board in-place and returns nothing.

Example 1

Before:           After:
X X X X           X X X X
X O O X    ->     X X X X
X X O X           X X X X
X O X X           X O X X

Input: board = [["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 bottom-left 'O' touches the border so it is not captured. The interior 'O's are surrounded and become 'X'.

Example 2

Input: board = [["X"]]
Output: [["X"]]
Explanation: A single 'X' cell - nothing to capture.

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'

Hints