Description

Given a 2D board containing 'X' and 'O' (the letter 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

DFS

Surrounded region怎么定义？从某个'O'往四周开始扩散，如果没有遇到边界，这就是一个surrounded region。但是这样做未免有点麻烦，换一个思路想，如果边界上有'O'，那么与它联通的'O'们必定不是surrounded，先找出这种位置并标记成一个中间值'*'，那么剩下没有被标记的'O'即为所求，flip掉即可。

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        
        int m = board.length;
        int n = board[0].length;
        // expand from boundry
        for (int i = 0; i < m; ++i) {
            dfsExpand(board, i, 0);
            dfsExpand(board, i, n - 1);
        }
        
        for (int j = 1; j < n - 1; ++j) {
            dfsExpand(board, 0, j);
            dfsExpand(board, m - 1, j);
        }
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '*') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    public void dfsExpand(char[][] board, int i, int j) {
        if (i < 0 || i == board.length || j < 0 || j == board[0].length 
            || board[i][j] != 'O') {
            return;
        }
        
        board[i][j] = '*';
        dfsExpand(board, i - 1, j);
        dfsExpand(board, i + 1, j);
        dfsExpand(board, i, j - 1);
        dfsExpand(board, i, j + 1);        
    }
}

BFS

同样的思路很容易就能扩展到BFS上。

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        
        int m = board.length;
        int n = board[0].length;
        Queue<int[]> queue = new LinkedList<>();
        
        for (int i = 0; i < m; ++i) {
            bfsExpand(board, i, 0, queue);
            bfsExpand(board, i, n - 1, queue);
        }
        
        for (int j = 1; j < n - 1; ++j) {
            bfsExpand(board, 0, j, queue);
            bfsExpand(board, m - 1, j, queue);
        }
        
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            bfsExpand(board, pos[0] - 1, pos[1], queue);
            bfsExpand(board, pos[0] + 1, pos[1], queue);
            bfsExpand(board, pos[0], pos[1] - 1, queue);
            bfsExpand(board, pos[0], pos[1] + 1, queue);
            
        }
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '*') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    
    public void bfsExpand(char[][] board, int i, int j, Queue<int[]> queue) {
        if (i < 0 || i == board.length || j < 0 || j == board[0].length 
            || board[i][j] != 'O') {
            return;
        }
        
        board[i][j] = '*';
        queue.offer(new int[] {i, j});        
    }
}

Union-Find

也可以用union-find的思路来解这道题，数组中的'O'形成了若干个连通区，如果某个连通区包含在数组boundary上的节点，那么这个连通区不需要被flip。

如何判断某个连通区是否包含boundary上的节点呢？有一个很聪明的做法是，将boundary 'O'节点统统连到一个dummy node上，这样只需要判断是否跟dummy node连通即可。

class Solution {
    public static final int[][] DIRECTIONS = {{1, 0}, {0, 1}};
    
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        
        int m = board.length;
        int n = board[0].length;
        UnionFind uf = new UnionFind(m * n + 1);
        int dummyNode = m * n;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] != 'O') {
                    continue;
                }
                // connect boundary 'O' to the dummy node component
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    uf.union(getIndex(i, j, n), dummyNode);    
                }
                
                for (int[] direction : DIRECTIONS) {
                    int x = i + direction[0];
                    int y = j + direction[1];

                    if (isValid(x, y, m, n) && board[x][y] == 'O') {
                        uf.union(getIndex(i, j, n), getIndex(x, y, n));
                    }
                }
            }
        }
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                // expect the dummy node component, others should be flipped
                if (!uf.isConnected(getIndex(i, j, n), dummyNode)) {
                    board[i][j] = 'X';
                }
            }
        }
    }
    
    public int getIndex(int i, int j, int cols) {
        return i * cols + j;
    }
    
    public boolean isValid(int i, int j, int m, int n) {
        return i >= 0 && i < m && j >= 0 && j < n;
    }
    
    class UnionFind {
        int[] parent;
        
        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
            }
        }
        
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        public void union(int x, int y) {
            parent[find(x)] = parent[find(y)];
        }
        
        public boolean isConnected(int x, int y) {
            return find(x) == find(y);
        }
    }
}