Surrounded Regions
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 in that surrounded region.

30:00

Surrounded Regions
medium
Topics
Companies

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 in that surrounded region.

Example 1:
Input: [["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"]]
Constraints:

  • m==board.lengthm == \text{board.length}

  • n==board[i].lengthn == \text{board}[i].\text{length}

  • 1≤m,n≤2001 \leq m, n \leq 200

  • board[i][j]∈{’X’,’O’}\text{board}[i][j] \in \{\text{'X'}, \text{'O'}\}

Input
arr =[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]

X

X

X

X

X

O

O

X

X

X

O

X

X

O

X

X

X (Captured)
O (Region)
T (Safe)
Phase: border

Mark border-connected Os as safe (T)

Variables
VariableValue
m4
n4
DepthFunction Call
Stack empty
0/3