Surrounded Regions

medium

You are given an m x n matrix board containing letters '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 in that surrounded region. A region is not captured if any of its cells touches the border of the board.

Test Cases

Copy an input into the main harness and Run to verify

Input

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

Expected Output

[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

Explanation: The O on the bottom border survives, and so would anything connected to it.

Input

board = [["X"]]

Expected Output

[["X"]]

Constraints

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

Hints

Hint 1 — click to reveal

It is much easier to find the regions that *survive* than the ones that get captured.

Hint 2 — click to reveal

Any 'O' reachable from the border is safe — flood fill inward from the edges.

Java Compiler