Gogo game – 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
Solution

First question to yourself is which ‘O’ cells would or would not be flipped to ‘X’.

According to the definition, if ‘O’ cell is surrounded by ‘X’ cells, i.e. up/down/left/right cells are ‘X’.
The first thought could be for each ‘O’ cell, add it to an array, check its up/down/left/right and if it is another ‘O’ cell, continue until, it hits all ‘X’ cells or it hits boundary. In the former case, cells in the array can all be flipped to’X’; while in the latter case, cells in the array cannot be flipped.

But it is not easy to check cells in the middle of board.
Notice that any ‘O’ cells that connected (directly or indirectly) to a boundary ‘O’ cell can not be flipped. So, we don’t need to keep track of both flip-able and non-flip-able ‘O’ cells. We can start from boundary cells and use BFS or DFS to find out all its neighbor ‘O’ cells — those are the non-flip-able ‘O’ cells!

The algorithm will be something like:
Start from those boundary cells, use BFS or DFS to traverse all non-flipable ‘O’ cells, and mark them with a special sign, say ‘N’.
Revisit the board, flip all remaining ‘O’ cells to ‘X’ and also flip back ‘N’ cells to ‘O’.
Notice that for each boundary cell, no matter what value it has, it will never be flipped. Also, for the four corner cells, their value will not impact any other cells.
So, we can improve the above algorithm a little bit: only mark non-boundary cells and then only flip non-boundary ‘O’ and ‘N’ cells.

<

pre>
private void mark(char[][] board, int row, int col, Queue que) {
if (board[row][col] != 'O') {
return;
}
board[row][col] = 'N';
int columns = board[0].length;
que.offer(row * columns + col);
}

private void markBFS(char[][] board, int row, int col) {
Queue que = new LinkedList();
mark(board, row, col, que);
int rows = board.length, columns = board[0].length;
while (!que.isEmpty()) {
int cell = que.poll();
int x = cell / columns, y = cell % columns;
// push its neighbors to stack if needed
if (x+1 < rows-1) mark(board, x+1, y, que);
if (x-1 > 0) mark(board, x-1, y, que);
if (y+1 < columns-1) mark(board, x, y+1, que);
if (y-1 > 0) mark(board, x, y-1, que);
}
}

private void markDFS(char[][] board, int x, int y) {
if (board[x][y] != 'O') {
return;
}
// mark the current node
board[x][y] = 'N';
// mark its neighbors if needed
int rows = board.length, columns = board[0].length;
if (x+1 < rows-1) markDFS(board, x+1, y);
if (x-1 > 0) markDFS(board, x-1, y);
if (y+1 < columns-1) markDFS(board, x, y+1);
if (y-1 > 0) markDFS(board, x, y-1);
}

public void solve(char[][] board) {
if (board.length <= 0 || board[0].length <= 0) return;
int rows = board.length, columns = board[0].length;

// Start from 'O's on the edge and mark connected ones as non-flipable.
// first and last columns
for (int i=1; columns>2 && i<rows-1; ++i) {
if (board[i][0] == 'O') markBFS(board, i, 1);
if (board[i][columns-1] == 'O') markBFS(board, i, columns-2);
}
// first and last rows
for (int j=1; rows>2 && j<columns-1; ++j) {
if (board[0][j] == 'O') markBFS(board, 1, j);
if (board[rows-1][j] == 'O') markBFS(board, rows-2, j);
}

// flip
for (int i=1; i<rows-1; ++i) {
for (int j=1; j<columns-1; ++j) {
if (board[i][j] == 'O') {
board[i][j] = 'X';
} else if (board[i][j] == 'N') {
board[i][j] = 'O';
}
}
}
}

Leave a Reply

Your email address will not be published. Required fields are marked *