Surrounded Regions
MediumGraphs
You are given an m x n board whose cells are either "X" or "O".
A region is a group of "O" cells connected horizontally or vertically (not diagonally). A region is surrounded if none of its cells lies on the outer edge of the board (the first or last row, or the first or last column). Because a surrounded region has no cell on the edge, it is completely enclosed by "X" cells.
Capture every surrounded region by changing all of its cells to "X". Any region with at least one cell on the edge stays exactly as it is. Return the resulting board. You may modify board in place and return it.
Example 1
- Input:
- board = [["X", "X", "X", "X", "X"], ["X", "O", "O", "X", "X"], ["X", "X", "O", "X", "O"], ["X", "O", "X", "O", "O"], ["X", "X", "X", "X", "X"]]
- Output:
- [["X", "X", "X", "X", "X"], ["X", "X", "X", "X", "X"], ["X", "X", "X", "X", "O"], ["X", "X", "X", "O", "O"], ["X", "X", "X", "X", "X"]]
- Explanation
- The three connected
Ocells near the top-left and the loneOat row 3, column 1 touch no edge, so they are captured. TheOcells at row 2, column 4 and row 3, columns 3-4 form one region that reaches the right edge, so they stay.
Example 2
- Input:
- board = [["X", "O", "X", "X"], ["X", "O", "O", "X"], ["X", "X", "O", "X"], ["X", "X", "X", "X"]]
- Output:
- [["X", "O", "X", "X"], ["X", "O", "O", "X"], ["X", "X", "O", "X"], ["X", "X", "X", "X"]]
- Explanation
- The
Oat the top edge is connected through row 1 down to row 2, column 2, so that whole region touches the edge and nothing is captured.
Example 3
- Input:
- board = [["X", "X", "X"], ["X", "O", "X"], ["X", "X", "X"]]
- Output:
- [["X", "X", "X"], ["X", "X", "X"], ["X", "X", "X"]]
- Explanation
- The centre
Ois enclosed on all four sides, so it is captured.
Constraints
m == board.length,n == board[i].length- 1 ≤
m,n≤ 200 board[i][j]is"X"or"O"