wayetan
2/19/2014 - 10:20 AM

## Surrounded Regions

Surrounded Regions

``````/**
* 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
*/
public class Solution {
private Queue<Integer> queue = new LinkedList<Integer>();
public void solve(char[][] board) {
if(board == null || board.length == 0)
return;
int row = board.length, col = board[0].length;
for(int i = 0; i < row; i++) {
if(board[i][0] == 'O') {
bfs(board, i, 0);
}
if(board[i][col - 1] == 'O'){
bfs(board, i, col - 1);
}
}
for(int i = 0; i < col; i++) {
if(board[0][i] == 'O') {
bfs(board, 0, i);
}
if(board[row - 1][i] == 'O') {
bfs(board, row - 1, i);
}
}
for(int i = 0; i < row; i++) {
for(int j = 0; j < col; j++) {
if(board[i][j] == 'O') {
board[i][j] = 'X';
}
if(board[i][j] == 'P') {
board[i][j] = 'O';
}
}
}
}
private void bfs(char[][] board, int i, int j) {
int col = board[0].length;
fill(board, i, j);
while(!queue.isEmpty()) {
int cur = queue.poll();
int x = cur / col;
int y = cur % col;
fill(board, x - 1, y);
fill(board, x + 1, y);
fill(board, x, y + 1);
fill(board, x, y - 1);
}
}
private void fill(char[][] board, int i, int j) {
int row = board.length;
int col = board[0].length;
if(i < 0 || i >= row || j < 0 || j >= col || board[i][j] != 'O')
return;
queue.offer(i * col + j);
board[i][j] = 'P';
}

// an easier way to program this
public void solve(char[][] board) {
if(board.length == 0) return;
for(int i = 0; i < board[0].length; i++){
helper(board, 0 , i);
}
for(int i = 1; i < board.length; i++) {
helper(board, i, board[0].length - 1);
}
for(int i = 0; i < board[0].length - 1; i++) {
helper(board, board.length - 1, i);
}
for(int i = 1; i < board.length - 1; i++) {
helper(board, i, 0);
}
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
board[i][j] = (board[i][j] == 'M') ? 'O' : 'X';
}
}
return;
}
public void helper(char[][] board, int a, int b) {
if(board[a][b] == 'X' || board[a][b] == 'M')  return;
board[a][b] = 'M'; // mark as visited
if(a + 1 < board.length)    helper(board, a + 1, b);
if(a - 1 > 0)   helper(board, a - 1, b);
if(b + 1 < board[0].length)     helper(board, a, b + 1);
if(b - 1 > 0)   helper(board, a, b - 1);
}
}
``````