Surrounded Regions

Question

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.

Example

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

After capture all regions surrounded by 'X', the board should be:

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

Tags

Breadth First Search Union Find

Related Problems

Hard Number of Islands II Easy Number of Islands

Analysis

本题也是一个多解的问题。

一种比较巧妙的思路是从边缘的'O'出发，通过DFS，所有能够遍历的'O'都可以暂时被标记为'#'，那么剩下未能被标记的'O'说明被surrounded，需要在遍历结束之后全部转为'X'。（用DFS或者BFS要警惕栈溢出）

另一种方法是用Union Find，将与边缘相连通的'O'全部union到一个dummy node（也可以用hasEdge[]来存储，不过内存占用更多）, 最终将没有和这个dummy node是一个component的'O'点全部标记为'X'。

Solution

DFS - (7ms AC 42.74%)

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;

        // Marking 'O' on the boundary and connected as '*'
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') {
                marking(board, i, 0);
            }
            if (board[i][n - 1] == 'O') {
                marking(board, i, n - 1);
            }
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                marking(board, 0, j);
            }
            if (board[m - 1][j] == 'O') {
                marking(board, m - 1, j);
            }
        }

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

        // Replacing '*' as 'X'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == '*') {
                    board[i][j] = 'O';
                }
            }
        }

    }

    // DFS marking 'O' as '*'
    private void marking (char[][] board, int x, int y) {
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int nx, ny;
        if (board[x][y] == 'O') {
            board[x][y] = '*';
            for (int i = 0; i < 4; i++) {
                nx = x + dx[i]; 
                ny = y + dy[i];
                if (nx >= 0 && ny >= 0 && nx < board.length && ny < board[0].length) {
                    marking(board, nx, ny);
                }
            } 
        }
    }
}

DFS - (4ms AC 100%)

class Solution {
    public void solve(char[][] board) {

        if (board.length < 1 || board[0].length < 1)
            return;
        for (int i = 0; i < board.length; i++) {
            if (board[i][0] != 'X');
            dfsmarker(i, 0, board);
        }
        for (int i = 0; i < board.length; i++) {
            if (board[i][board[0].length - 1] != 'X')
                dfsmarker(i, board[0].length - 1, board);
        }
        for (int j = 0; j < board[0].length; j++) {
            if (board[0][j] != 'X');
            dfsmarker(0, j, board);
        }
        for (int j = 0; j < board[0].length; j++) {
            if (board[board.length - 1][j] != 'X')
                dfsmarker(board.length - 1, j, board);
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                //System.out.println(marker[i][j]);
                if (board[i][j] == 'M')
                    board[i][j] = 'O';
                else
                    board[i][j] = 'X';
            }

        }
        //System.out.println(marker[1][1]);
        return;


    }
    public void dfsmarker(int i, int j, char[][] board) {
        if (board[i][j] == 'M' || board[i][j] != 'O')
            return;

        board[i][j] = 'M';
        if (i > 0)
            dfsmarker(i - 1, j, board);
        if (j > 0)
            dfsmarker(i, j - 1, board);
        if (i < board.length - 1)
            dfsmarker(i + 1, j, board);
        if (j < board[0].length - 1)
            dfsmarker(i, j + 1, board);
    }

}

DFS - Cleaner Version (6ms 59.18%)

class Solution {
    public void solve(char[][] board) {
        if (board.length == 0 || board[0].length == 0) return;
        if (board.length < 3 || board[0].length < 3) return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') helper(board, i, 0);
            if (board[i][n - 1] == 'O') helper(board, i, n - 1);
        }
        for (int j = 1; j < n - 1; j++) {
            if (board[0][j] == 'O') helper(board, 0, j);
            if (board[m - 1][j] == 'O') helper(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';
                if (board[i][j] == '*') board[i][j] = 'O';
            }
        }
    }

    private void helper(char[][] board, int r, int c) {
        if (r < 0 || c < 0 || r > board.length - 1 || c > board[0].length - 1 || board[r][c] != 'O') return;
        board[r][c] = '*';
        helper(board, r + 1, c);
        helper(board, r - 1, c);
        helper(board, r, c + 1);
        helper(board, r, c - 1);
    }
}

Union Find (20 ms 14.75% AC)

class UnionFind {
    private int[] id;
    private int[] size;

    public UnionFind(int n) {
        id = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    public int find(int i) {
        while (i != id[i]) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }

    public void union(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i == j) {
            return;
        }
        if (size[i] < size[j]) {
            id[i] = j;
            size[j] += size[i];
        } else {
            id[j] = i;
            size[i] += size[j];
        }
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

public class Solution {

    private boolean isEdge(int M, int N, int i, int j) {
        return (i == 0 || i == M - 1 || j == 0 || j == N - 1);
    }

    private boolean insideBoard(int M, int N, int i, int j) {
        return (i < M && i >= 0 && j < N && j >= 0);
    }
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     */
    public void surroundedRegions(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        int M = board.length;
        int N = board[0].length;

        int[] dirX = {0, 0, -1, 1};
        int[] dirY = {-1, 1, 0, 0};

        UnionFind uf = new UnionFind(M * N + 1);


        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == 'O') {
                    if (isEdge(M, N, i, j)) {
                        uf.union(i * N + j, M * N);
                    } else {
                        for (int k = 0; k < 4; k++) {
                            int x = i + dirX[k];
                            int y = j + dirY[k];
                            if (insideBoard(M, N, x, y) && board[x][y] == 'O') {
                                uf.union(i * N + j, x * N + y);
                            }
                        }
                    }
                }
            }
        }

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!uf.connected(i * N + j, M * N)) {
                    board[i][j] = 'X';
                }
            }
        }

    }
}

Reference

• LeetCode Discussion: Solve it using Union Find

• Flood Fill Algorithm

• 水中的鱼 Surrounded Regions, Solution BFS

• 喜刷刷 Surrounded Regions

• programcreek: LeetCode – Surrounded Regions