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

Another example,

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

After running your function, the board should be:

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

Update: 2016-09-27

In fact both DFS and BFS is acceptable. However, DFS is much faster. The idea is similar. Adding all "free nodes" (nodes that don't need to be flipped) on the edge to the queue. Using DFS to find all neighbors of "free nodes" and adding them to queue too, since these nodes should not be flipped either. Then just flip all other Os to Xs.

public void solve(char[][] board) { if(board == null || board.length == 0) return; int cols = board[0].length; int rows = board.length; Queue freeNodes = new LinkedList(); for(int j = 0; j < cols; j++){ enqueue(0, j, board, freeNodes); enqueue(rows - 1, j, board, freeNodes); } for(int i = 0; i < rows; i++){ enqueue(i, 0, board, freeNodes); enqueue(i, cols - 1, board, freeNodes); } while(!freeNodes.isEmpty()){ int n = freeNodes.poll(); int x = n / cols; int y = n % cols; enqueue(x + 1, y, board, freeNodes); enqueue(x - 1, y, board, freeNodes); enqueue(x, y + 1, board, freeNodes); enqueue(x, y - 1, board, freeNodes); } for (int i = 0; i < rows; i++){ for (int j = 0; j < cols; j++){ if(board[i][j] == 'O') board[i][j] = 'X'; else if(board[i][j] == 'D') board[i][j] = 'O'; } } } private void enqueue(int x, int y, char[][] board, Queue freeNodes){ if(x >= 0 && x < board.length && y >= 0 && y < board[0].length && board[x][y] == 'O'){ board[x][y] = 'D'; freeNodes.add(x * board[0].length + y); } }


I had some problem understanding what the "surrounded regions" means. At first glance, I thought it means the 'O' is surrounded by all 'X's, which doesn't make sense for two consecutive 'O's. Then I thought may be it means after I flip the first 'O'? However, in the example, all 'O's are surrounded by at least another 'O'. The only possibility is, all the 'O' s are surrounded by 'X's, which means only the 'O's at boarders and those surrounded by these 'O's will not be flipped.

The approach is: BFS.
We search the boarders first, mark the 'O', and if the boarder 'O' has neighbor 'O's (upper, left, right, down), mark them too.
After that, we simply search the rest board and flip 'O's to 'X's.

public class FlipO {
    static final int[] X_axis = {1, -1, 0, 0};
    static final int[] Y_axis = {0, 0, 1, -1};
    static final char FREE_NODE = 'F';
    static final char TRAVELED_NODE = 'T';
    //I declared a class for coordinates of characters on the board
    static class Node
    {
        int x;
        int y;
        public Node(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }
    public void solve(char[][] board) {
        if (board == null || board.length <= 1 || board[0].length <= 1)
            return;
        int rows = board.length;
        int cols = board[0].length;
        for (int i = 0; i < rows; i++)
        {
            findFreeNode(board, i, 0);
            findFreeNode(board, i, cols - 1);
        }
        for (int j = 1; j < cols - 1; j++)
        {
            findFreeNode(board, 0, j);
            findFreeNode(board, rows - 1, j);
        }
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                switch(board[i][j])
                {
                    case 'O':
                        board[i][j] = 'X';
                        break;
                    case 'F':
                        board[i][j] = 'O';
                }
            }
        }
        
    }
    //BFS
    private void findFreeNode(char[][] board, int x, int y)
    {
        //May equal 'T', 'F'
        if (board[x][y] != 'O')
            return;
        Queue queue = new LinkedList();
        queue.offer(new Node(x, y));
        while (!queue.isEmpty())
        {
            Node curr = queue.poll();
            board[curr.x][curr.y] = FREE_NODE;
            for (Node neighbor : neighborList(board, curr))
                queue.offer(neighbor);
        }
    }
    private ArrayList neighborList(char[][] board, Node curr)
    {
        ArrayList list = new ArrayList();
        for (int i = 0; i < X_axis.length; i++)
        {
            int x = curr.x + X_axis[i];
            int y = curr.y + Y_axis[i];
            if (x >= 0 && x < board.length && 
            y >= 0 && y < board[0].length && board[x][y] == 'O')
            {
                list.add(new Node(x, y));
                board[x][y] = TRAVELED_NODE;
            }
        }
        return list;
    }
}