GuilinDev

Lc0130

05 August 2008

130 Surrounded Regions

题目

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.

Example:

1
2
3
4

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

After running your function, the board should be:

1
2
3
4

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

Explanation:

Surrounded regions shouldn’t be on the border, which means that any ‘O’ on the border of the board are not flipped to ‘X’. Any ‘O’ that is not on the border and it is not connected to an ‘O’ on the border will be flipped to ‘X’. Two cells are connected if they are adjacent cells connected horizontally or vertically.

分析

题目中解释说被包围的区间不会存在于边界上，边界有0代表连通，所以我们会想到边界上的 O 要特殊处理，只要把边界上的 O 特殊处理了，那么剩下的 O 替换成 X 就可以了。所以只需要记住从四条边出发。

依然是DFS，BFS和Union Find。

代码

1) DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        int rows = board.length;
        int cols = board[0].length;
        // 从边缘开始DFS，flip相连的'O'
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                boolean isEdge = (i == 0 || i == rows - 1 || j == 0 || j == cols - 1);
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, j);
                }
            }
        }
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 正常for循环flip可能剩下的'O'
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
                // 之前DFS中跟边缘'O'相连的元素表示不应该被flip，并且被临时改成了'#'表示访问过，现在改回正确的值
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                }
            }
        }
    }
    private void dfs(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] = '#'; // 用额外数组记录也可以
        
        dfs(board, i - 1, j); // 上
        dfs(board, i + 1, j); // 下
        dfs(board, i, j - 1); // 左
        dfs(board, i, j + 1); // 右
    }
}

DFS用stack锻炼下，不太推荐

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

class Solution {
    public class Pos{
        int i;
        int j;
        Pos(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length;
        int n = board[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 从边缘第一个是o的开始搜索
                boolean isEdge = i == 0 || j == 0 || i == m - 1 || j == n - 1;
                if (isEdge && board[i][j] == 'O') {
                    dfs(board, i, 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';
                }
            }
        }
    }

    public void dfs(char[][] board, int i, int j) {
        Stack<Pos> stack = new Stack<>();
        stack.push(new Pos(i, j));
        board[i][j] = '#';
        while (!stack.isEmpty()) {
            // 取出当前stack 顶, 不弹出.
            Pos current = stack.peek();
            // 上
            if (current.i - 1 >= 0 
                && board[current.i - 1][current.j] == 'O') {
                stack.push(new Pos(current.i - 1, current.j));
                board[current.i - 1][current.j] = '#';
              continue;
            }
            // 下
            if (current.i + 1 <= board.length - 1 
                && board[current.i + 1][current.j] == 'O') {
                stack.push(new Pos(current.i + 1, current.j));
                board[current.i + 1][current.j] = '#';      
                continue;
            }
            // 左
            if (current.j - 1 >= 0 
                && board[current.i][current.j - 1] == 'O') {
                stack.push(new Pos(current.i, current.j - 1));
                board[current.i][current.j - 1] = '#';
                continue;
            }
            // 右
            if (current.j + 1 <= board[0].length - 1 
                && board[current.i][current.j + 1] == 'O') {
                stack.push(new Pos(current.i, current.j + 1));
                board[current.i][current.j + 1] = '#';
                continue;
            }
            // 如果上下左右都搜索不到,本次搜索结束，弹出stack
            stack.pop();
        }
    }
}

2) BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

class Solution {
    int m = 0;  // 行数
    int n = 0;  // 列数
    // 用作控制4个方向
    int[] dx = {1, -1, 0, 0};
    int[] dy = {0, 0, 1, -1};
    public void solve(char[][] board) {
        // java二维矩阵的行数和列数可能不同，并且每一行的列数可能都不一样
        // 但是肯定是先后行再有列，而且根据题目要求，在这里每一行的列数都是相同的
        m = board.length;       //  行数m
        if (m == 0) {   // 行数为0，board为空
            return;
        }
        n = board[0].length;    // 列数
        Queue<int[]> queue = new LinkedList<int[]>();
        // 搜索上下边界，先将O标记为M后入队
        for (int i = 0; i < n; i++) {
            if (board[0][i] == 'O') {   //  第一行
                board[0][i] = 'M';
                queue.offer(new int[]{0, i});
            }
            if (board[m - 1][i] == 'O') {      // 最后一行
                board[m - 1][i] = 'M';
                queue.offer(new int[]{m - 1, i});
            }
        }
        // 搜索左右边界，先将O标记为M后入队，
        // 注意i从1开始到m-1结束，j同样，表示和行相交的地方不要重复入队
        for (int i = 1; i < m - 1; i++) {
            if (board[i][0] == 'O') {   // 第一列
                board[i][0] = 'M';
                queue.offer(new int[]{i, 0});
            }
            if (board[i][n - 1] == 'O') {   // 最后一列
                board[i][n - 1] = 'M';
                queue.offer(new int[]{i, n - 1});
            }
        }
        // 从刚才已经入队的边缘元素开始广度优先搜索扩散
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int x = temp[0], y = temp[1];   // 获取行和列
            for (int i = 0; i < 4; i++) {   // 搜索四个方向
                int mx = x + dx[i], my = y + dy[i]; 
                if (mx < 0 || mx >= m || my < 0 || my >= n) {     // 越界
                    continue;
                } else if (board[mx][my] == 'O') {  // 搜索到了'O'，标记后入队
                    board[mx][my] = 'M';
                    queue.offer(new int[]{mx, my});
                }
            }
        }
        // 标记完，再次遍历，现在矩阵中可能有3中字符，'X','M','O'
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'X') {
                    continue;
                } else if (board[i][j] == 'O'){ // 出现没被标记过的'O'，应该被填充
                    board[i][j] = 'X';
                } else if (board[i][j] == 'M'){ // 被标记过的，不应该被填充，恢复
                    board[i][j] = 'O';
                }
            }
        }
    }
}

3) Union Find，dummy是一个虚拟节点，所有边界上有出口的表示不需要覆盖的和它union，最后再遍历一遍，没有和dummy相连(用find来返回值)的就置为’X’。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

class Solution {
    public void solve(char[][] board) {
        int row = board.length;
        if (row == 0) {
            return;
        }
        int col = board[0].length;
        int dummy = row * col;
        int[][] dirs = new int[][]{ {1, 0}, {0, 1}, {0, -1}, {-1, 0} };
        UnionFind uf = new UnionFind(dummy);

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (board[i][j] == 'O') {
                    if (i == 0 || i == row - 1 || j == 0 || j == col - 1) {
                        uf.union(i * col + j, dummy);
                    } else {
                        for (int k = 0; k < 4; k++) {
                            int x = i + dirs[k][0];
                            int y = j + dirs[k][1];
                            if (board[x][y] == 'O') {
                                uf.union(x * col + y, i * col + j);
                            }
                        }
                    }
                }
            }
        }
        for (int i = 1; i < row - 1; i++) {
            for (int j = 1; j < col - 1; j++) {
                if (!uf.connect(i * col + j, dummy)) {
                    board[i][j] = 'X';
                }
            }
        }
    }
}

// 以下是并查集的代码
class UnionFind {
    private int[] parent;

    public UnionFind(int dummy) {
        parent = new int[dummy + 1];
        for (int i = 0; i <= dummy; i++) {
            parent[i] = i;
        }
    }

    public void union(int x, int y) {
        int root_x = find(x);
        int root_y = find(y);
        if (root_x != root_y) {
            parent[root_x] = root_y;
        }
    }

    public int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    public boolean connect(int x, int y) {
        return find(x) == find(y);
    }
}
This site is open source. Improve this page.