# Question

Formatted question description: https://leetcode.ca/all/130.html

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: 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"]]
Explanation: Notice that an 'O' should not be flipped if:
- It is on the border, or
- It is adjacent to an 'O' that should not be flipped.
The bottom 'O' is on the border, so it is not flipped.
The other three 'O' form a surrounded region, so they are flipped.


Example 2:

Input: board = [["X"]]
Output: [["X"]]


Constraints:

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

# Algorithm

This problem is similar to the game of “Go” chess where enclosed stones are captured by the opponent. Here, we need to flip all the surrounded Os to Xs, except for those on the border.

We can solve this problem using Depth-First Search (DFS), similar to the previous problem of counting the number of islands. One approach could be to start DFS from each O in the middle of the matrix. If it reaches the border, we change all the visited Os back to O. If it doesn’t reach the border, we mark all visited Os as a different character, say $, so that they can be later identified as surrounded Os. However, this approach can be very expensive. A common practice seen on the internet is to scan the four sides of the matrix for Os. Whenever an O is found, use DFS to traverse and mark all connected Os as$. This way, all surrounded Os can be identified and changed to X, while the border Os remain unchanged. Finally, we can change all remaining Os marked as \$ back to O.

# Code

• import java.util.HashSet;
import java.util.Queue;

public class Surrounded_Regions {

public class Solution_bfs {

// record visited positions
HashSet<String> hs = new HashSet<String> ();

// BFS, using queue
public void solve(char[][] board) {
if (board == null || board.length == 0)     return;

int row = board.length;
int column = board.length;

// search each edge
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {

// find edge
if (i == 0 || i == row - 1 || j  == 0 || j == column - 1) {

if (board[i][j] == 'O') {

// key is compressed as "i_j"
if (!hs.contains(getKey(i, j))) {

// @note: like doing add when enqueue, also dont add it here, add ONLY happens after dequeue
BFS(board, i, j);
}
}
}
}
}

// if a position is not in hashset, then its "X"
for (int i = 0; i < row; i++) {
for (int j = 0; j < column; j++) {

if (!hs.contains(getKey(i, j)))
board[i][j] = 'X';
}
}

}

public void BFS (char[][] board, int inow, int jnow) {

q.offer(getKey(inow, jnow));

while (!q.isEmpty()) {
String keycode = q.poll();
String[] array = keycode.split("_");
int i = Integer.parseInt(array), j = Integer.parseInt(array);

if (board[i][j] == 'O' && !hs.contains(getKey(i, j))) {

// search neighbours of this position, find "O" and enqueue
//@note: dont consider positions on edge, since they are safe. just enqueue those NOT-edge
//      I was messed up by checking elements on edge, but no need
if (isValid(i + 1, j, board) && board[i + 1][j] == 'O' && !hs.contains(getKey(i + 1, j)))
{
q.offer(getKey(i + 1, j));

/*
@note: dont add to hashset here, if add here, next dequeue and get this one,
it's not going to search its neighbours since it is in hashset
*/
}

if (isValid(i - 1, j, board) && board[i - 1][j] == 'O' && !hs.contains(getKey(i - 1, j)))
{   q.offer(getKey(i - 1, j));  /* hs.add(getKey(i - 1, j));*/ }

if (isValid(i, j + 1, board) && board[i][j + 1] == 'O' && !hs.contains(getKey(i, j + 1)))
{   q.offer(getKey(i, j + 1));  /* hs.add(getKey(i, j + 1));*/ }

if (isValid(i, j - 1, board) && board[i][j - 1] == 'O' && !hs.contains(getKey(i, j - 1)))
{   q.offer(getKey(i, j - 1));  /* hs.add(getKey(i, j + 1));*/ }
}

}
}

public boolean isValid(int i, int j, char[][] board) {
int row = board.length;
int column = board.length;

if (i >= row || i < 0 || j >= column || j < 0)
return false;
else
return true;
}

public String getKey(int i, int j) {

return i+"_"+j;
}
}

// re-write dfs, check validity before next recursion. no bird use
public class Solution_dfs_improved {
public void solve(char[][] board) {

if (board.length == 0 || board.length == 0) {
return;
}
// if 'O' is somehow connected to boarder, then it's alive. NOT the same as GO chess

// if a single 'O' is alive, mark it as '.', then change it back to 'O' after flipping those trapped ones

int rowNum = board.length;
int colNum = board.length;

for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {

// try dfs on all 'O's on 4 boarders
if ((i == 0 || i == rowNum - 1 || j == 0 || j == colNum - 1)
&& board[i][j] == 'O') { // @note: accelaration is, if previous dfs modified some 'O', then no repeat dfs
// System.out.println("before one dfs: " + Arrays.deepToString(board));
dfs(board, i, j);
}
}
}

// flip trapped 'O's
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {

if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}

// restore alive 'O's
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {

if (board[i][j] == '.') {
board[i][j] = 'O';
}
}
}

}

public void dfs(char[][] b, int i, int j) {

if (b[i][j] == 'O') {
b[i][j] = '.';
}

// isValid() will also check if visited
if (isValid(b, i + 1, j) && b[i + 1][j] == 'O')     dfs(b, i + 1, j);
if (isValid(b, i - 1, j) && b[i - 1][j] == 'O')     dfs(b, i - 1, j);
if (isValid(b, i, j + 1) && b[i][j + 1] == 'O')     dfs(b, i, j + 1);
if (isValid(b, i, j - 1) && b[i][j - 1] == 'O')     dfs(b, i, j - 1);
}

public boolean isValid(char[][] b, int i, int j) {
int row = b.length, col = b.length;

if (i >= row || i < 0 || j >= col || j < 0)
return false;
else
return true;
}
}

// stackoverflow at dfs
public class Solution_dfs_over_limit {
public void solve(char[][] board) {

if (board.length == 0 || board.length == 0) {
return;
}
// if 'O' is somehow connected to boarder, then it's alive. NOT the same as GO chess

// if a single 'O' is alive, mark it as '.', then change it back to 'O' after flipping those trapped ones

int rowNum = board.length;
int colNum = board.length;

for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {

// try dfs on all 'O's on 4 boarders
if ((i == 0 || i == rowNum - 1 || j == 0 || j == colNum - 1)
&& board[i][j] == 'O') { // @note: accelaration is, if previous dfs modified some 'O', then no repeat dfs
dfs(board, i, j);
}
}
}

// flip trapped 'O's
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {

if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}

// restore alive 'O's
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {

if (board[i][j] == '.') {
board[i][j] = 'O';
}
}
}

}

private void dfs(char[][] board, int i, int j) {

if (i < 0 || j < 0 || i >= board.length || j >= board.length) {
return;
}

// if it's 'X', dont't do dfs
if (board[i][j] != 'O') { // @note: i missed thsi check, and fill full board with '.' ...
return;
}

board[i][j] = '.';

dfs(board, i - 1, j);
dfs(board, i + 1, j);
dfs(board, i, j - 1);
dfs(board, i, j + 1);
}
}
}

############

class Solution {
private char[][] board;
private int m;
private int n;

public void solve(char[][] board) {
m = board.length;
n = board.length;
this.board = board;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if ((i == 0 || i == m - 1 || j == 0 || j == n - 1) && board[i][j] == 'O') {
dfs(i, j);
}
}
}
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (board[i][j] == '.') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}

private void dfs(int i, int j) {
board[i][j] = '.';
int[] dirs = {-1, 0, 1, 0, -1};
for (int k = 0; k < 4; ++k) {
int x = i + dirs[k];
int y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
dfs(x, y);
}
}
}
}

• // OJ: https://leetcode.com/problems/surrounded-regions/
// Time: O(MN)
// Space: O(MN)
class Solution {
public:
void solve(vector<vector<char>>& A) {
int M = A.size(), N = A.size(), dirs = { {0,1},{0,-1},{1,0},{-1,0} };
function<void(int, int)> dfs = [&](int x, int y) {
if (x < 0 || x >= M || y < 0 || y >= N || A[x][y] != 'O') return;
A[x][y] = '#';
for (auto &[dx, dy] : dirs) dfs(x + dx, y + dy);
};
for (int i = 0; i < M; ++i) dfs(i, 0), dfs(i, N - 1);
for (int j = 0; j < N; ++j) dfs(0, j), dfs(M - 1, j);
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
A[i][j] = A[i][j] == '#' ? 'O' : 'X';
}
}
}
};

• class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""

def dfs(i, j):
board[i][j] = '.'
for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and board[x][y] == 'O':
dfs(x, y)

m, n = len(board), len(board)
for i in range(m):
for j in range(n):
if board[i][j] == 'O' and (
i == 0 or i == m - 1 or j == 0 or j == n - 1
):
dfs(i, j)
for i in range(m):
for j in range(n):
if board[i][j] == 'O':
board[i][j] = 'X'
elif board[i][j] == '.':
board[i][j] = 'O'

############

class UnionFind():
def __init__(self, m, n):
self.dad = [i for i in range(0, m * n)]
self.rank = [0 for i in range(0, m * n)]
self.m = m
self.n = n

def find(self, x):

def union(self, xy):
rank = self.rank
x, y = map(self.find, xy)
if x == y:
return False
if rank[x] > rank[y]:
else:
if rank[x] == rank[y]:
rank[y] += 1
return True

class Solution:
# @param {list[list[str]]} board a 2D board containing 'X' and 'O'
# @return nothing
def solve(self, board):
if len(board) == 0:
return
regions = set([])
n, m = len(board), len(board)
uf = UnionFind(len(board), len(board))
directions = {"u": (-1, 0), "d": (1, 0), "l": (0, -1), "r": (0, 1)}
for i in range(0, len(board)):
for j in range(0, len(board)):
if board[i][j] == 'X':
continue
for d in ["d", "r"]:
di, dj = directions[d]
newi, newj = i + di, j + dj
if newi >= 0 and newi < len(board) and newj >= 0 and newj < len(board):
if board[newi][newj] == "O":
uf.union((newi * m + newj, i * m + j))

for i in range(0, len(board)):
for j in [0, len(board) - 1]:
if board[i][j] == "O":

for j in range(0, len(board)):
for i in [0, len(board) - 1]:
if board[i][j] == "O":

for i in range(0, len(board)):
for j in range(0, len(board)):
if board[i][j] == "O" and uf.find(i * m + j) not in regions:
board[i][j] = "X"


• func solve(board [][]byte) {
m, n := len(board), len(board)
var dfs func(i, j int)
dfs = func(i, j int) {
board[i][j] = '.'
dirs := []int{-1, 0, 1, 0, -1}
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' {
dfs(x, y)
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if (i == 0 || i == m-1 || j == 0 || j == n-1) && board[i][j] == 'O' {
dfs(i, j)
}
}
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if board[i][j] == '.' {
board[i][j] = 'O'
} else if board[i][j] == 'O' {
board[i][j] = 'X'
}
}
}
}

• /**
Do not return anything, modify board in-place instead.
*/
function solve(board: string[][]): void {
function dfs(i, j) {
board[i][j] = '.';
const dirs = [-1, 0, 1, 0, -1];
for (let k = 0; k < 4; ++k) {
const x = i + dirs[k];
const y = j + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O') {
dfs(x, y);
}
}
}
const m = board.length;
const n = board.length;
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (
(i == 0 || i == m - 1 || j == 0 || j == n - 1) &&
board[i][j] == 'O'
) {
dfs(i, j);
}
}
}
for (let i = 0; i < m; ++i) {
for (let j = 0; j < n; ++j) {
if (board[i][j] == '.') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}


• using System;
using System.Collections.Generic;

public class Solution {
private static readonly int[,] directions = new int[4, 2] { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
public void Solve(char[][] board) {
var lenI = board.Length;
var lenJ = lenI == 0 ? 0 : board.Length;

for (var i = 0; i < lenI; ++i)
{
for (var j = 0; j < lenJ; ++j)
{
if (board[i][j] == 'O')
{
var marked = new List<Tuple<int, int>>();
board[i][j] = 'M';
bool escaped = false;
for (var m = 0; m < marked.Count; ++m)
{
for (var k = 0; k < 4; ++k)
{
var newI = marked[m].Item1 + directions[k, 0];
var newJ = marked[m].Item2 + directions[k, 1];
if (newI < 0 || newI >= lenI || newJ < 0 || newJ >= lenJ)
{
escaped = true;
}
else if (board[newI][newJ] == 'O')
{
board[newI][newJ] = 'M';
}
}
}

if (!escaped)
{
foreach (var item in marked)
{
board[item.Item1][item.Item2] = 'X';
}
}
}
}
}

for (var i = 0; i < lenI; ++i)
{
for (var j = 0; j < lenJ; ++j)
{
if (board[i][j] == 'M')
{
board[i][j] = 'O';
}
}
}
}
}

• impl Solution {
fn dfs(i: usize, j: usize, mark: char, vis: &mut Vec<Vec<bool>>, board: &mut Vec<Vec<char>>) {
if vis[i][j] || board[i][j] != mark {
return;
}
vis[i][j] = true;
if i > 0 {
Self::dfs(i - 1, j, mark, vis, board);
}
if i < vis.len() - 1 {
Self::dfs(i + 1, j, mark, vis, board);
}
if j > 0 {
Self::dfs(i, j - 1, mark, vis, board);
}
if j < vis.len() - 1 {
Self::dfs(i, j + 1, mark, vis, board);
}
}

pub fn solve(board: &mut Vec<Vec<char>>) {
let m = board.len();
let n = board.len();
let mut vis = vec![vec![false; n]; m];
for i in 0..m {
Self::dfs(i, 0, board[i], &mut vis, board);
Self::dfs(i, n - 1, board[i][n - 1], &mut vis, board);
}
for i in 0..n {
Self::dfs(0, i, board[i], &mut vis, board);
Self::dfs(m - 1, i, board[m - 1][i], &mut vis, board);
}
for i in 0..m {
for j in 0..n {
if vis[i][j] {
continue;
}
board[i][j] = 'X';
}
}
}
}