All problems

Surrounded Regions

Medium · graph traversal

You are given a rectangular grid of characters, board. Every cell holds either "X" or "O".

A region is a group of "O" cells joined through shared edges: two "O" cells are in the same region if you can walk from one to the other by moving up, down, left or right over "O" cells only. Cells that touch only at a corner are not joined.

A region is surrounded if none of its cells is on the border of the grid, that is, none is in the first row, the last row, the first column or the last column. Capture every surrounded region by changing all of its cells to "X". Regions that have at least one cell on the border stay exactly as they are, and so does every "X".

Return the grid after the captures. The result is a new grid; the input does not need to be changed.

Examples

Example 1

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

The three joined "O" cells in the middle are enclosed by "X" cells, so they are captured. The "O" in the bottom row is on the border, so it stays.

Example 2

Input: board = [["O","X","O"], ["X","O","X"], ["O","X","O"]]

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

The centre "O" only touches the corner "O" cells diagonally, so it is a region of its own and nothing on its edges reaches the border.

Example 3

Input: board = [["O","O"], ["O","O"]]

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

Every cell is on the border, so nothing is captured.

Constraints