Description
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's. Return the result as a 2D array.
Examples
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]][["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]The 'O' at (3,1) sits in the bottom row, making it a border cell that cannot be captured. The 'O's at (1,1), (1,2), and (2,2) form a connected L-shaped region in the interior. Since this region has no path to any border 'O', it is completely surrounded by 'X' and gets flipped. The result preserves only the border 'O' at (3,1).
board = [["X"]][["X"]]A 1x1 board containing only X has no O cells to capture, so the board remains unchanged as [["X"]].
board = [["O","X","O","O"],["O","X","X","O"],["X","X","O","O"],["O","O","O","X"]][["O","X","O","O"],["O","X","X","O"],["X","X","O","O"],["O","O","O","X"]]Starting from border 'O's: (0,0), (0,2), (0,3), (1,0), (1,3), (2,2), (2,3), (3,0), (3,1), (3,2) are all either on the border or connected to border 'O's through adjacent cells. Tracing from (0,0)→(1,0) and from (0,3)→(1,3)→(2,3)→(2,2)→(3,2)→(3,1)→(3,0) shows all 'O's form one connected region touching the border. No 'O' is fully surrounded, so nothing is captured.
Constraints
- •
m == board.length - •
n == board[i].length - •
1 ≤ m, n ≤ 200