# Surrounded Regions

## Problem

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

## Code - Java

public class Solution {
/**
* @param board a 2D board containing 'X' and 'O'
* @return void
*/
public void surroundedRegions(char[][] board) {
if (board == null || board.length == 0) {
return;
}

int n = board.length;
int m = board.length;

boolean[][] visited = new boolean[n][m];

for (int i = 0; i < n; i++) {
if (board[i] == 'O') {
search(board, visited, i, 0);
}

if (board[i][m - 1] == 'O') {
search(board, visited, i, m - 1);
}
}

for (int j = 0; j < m; j++) {
if (board[j] == 'O') {
search(board, visited, 0, j);
}

if (board[n - 1][j] == 'O') {
search(board, visited, n - 1, j);
}
}

for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == '_') {
board[i][j] = 'O';
} else {
board[i][j] = 'X';
}
}
}
}

private void search(char[][] board, boolean[][] visited, int x, int y) {

int n = board.length;
int m = board.length;

int[] dx = new int[]{1, 0, -1, 0};
int[] dy = new int[]{0, 1, 0, -1};

qx.offer(x);
qy.offer(y);
visited[x][y] = true;

while (!qx.isEmpty()) {
int xx = qx.poll();
int yy = qy.poll();
board[xx][yy] = '_';

for (int i = 0; i < 4; i++) {
int nx = xx + dx[i];
int ny = yy + dy[i];

if (nx < n && nx >= 0 && ny < m && ny >= 0 && board[nx][ny] == 'O' && visited[nx][ny] == false) {
qx.offer(nx);
qy.offer(ny);
visited[nx][ny] = true;
}
}
}
}
}

public class Solution {

private int MAX_QUEUE = 100000;

public void solve(char[][] board) {
int xLen = board.length;
if (xLen == 0) return;
int yLen = board.length;

int[] qx = new int[MAX_QUEUE];
int[] qy = new int[MAX_QUEUE];
int tail = 0;
for (int i = 0; i < xLen; i++) {
if (board[i] == 'O') {
qx[tail] = i;
qy[tail] = 0;
tail++;
}
if (board[i][yLen - 1] == 'O') {
qx[tail] = i;
qy[tail] = yLen - 1;
tail++;
}
}
for (int i = 0; i < yLen; i++) {
if (board[i] == 'O') {
qx[tail] = 0;
qy[tail] = i;
tail++;
}
if (board[xLen - 1][i] == 'O') {
qx[tail] = xLen - 1;
qy[tail] = i;
tail++;
}
}

int[] dx = new int[]{1, -1, 0, 0};
int[] dy = new int[]{0, 0, 1, -1};

board[x][y] = 'N';
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 0 && nx < xLen && ny >= 0 && ny < yLen && board[nx][ny] == 'O') {
qx[tail] = nx;
qy[tail] = ny;
tail++;
}
}
}

for (int i = 0; i < xLen; i++) {
for (int j = 0; j < yLen; j++) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == 'N') {
board[i][j] = 'O';
}
}
}
}
}