Poison

130. Surrounded Regions

发表于
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
class Solution {
    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;

        for (int j = 0; j < n; j++) {
            dfs(board, m, n, 0, j);
            dfs(board, m, n, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            dfs(board, m, n, i, 0);
            dfs(board, m, n, i, n - 1);
        }

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

    private void dfs(char[][] board, int m, int n, int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] == 'X' || board[i][j] == 'E') {
            return;
        }

        board[i][j] = 'E';
        dfs(board, m, n, i + 1, j);
        dfs(board, m, n, i - 1, j);
        dfs(board, m, n, i, j + 1);
        dfs(board, m, n, i, j - 1);
    }
}
UnionFind
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
76
77
78
79
80
81
82
83
84
85
86
87
class Solution {
    private static class UnionFind {
        private final int[] parent;

        public UnionFind(int count) {
            this.parent = new int[count];
            for (int i = 0; i < count; i++) {
                this.parent[i] = i;
            }
        }

        public int getRoot(int x) {
            while (x != parent[x]) {
                parent[x] = parent[parent[x]]; // path compression
                x = parent[x];
            }
            return x;
        }

        public boolean isConnected(int x, int y) {
            return getRoot(x) == getRoot(y);
        }

        public void union(int x, int y) {
            int xRoot = getRoot(x);
            int yRoot = getRoot(y);
            if (xRoot == yRoot) {
                return;
            }

            parent[xRoot] = yRoot;
        }
    }

    private static final int[][] DIRECTIONS = new int[][]{{0, 1}, {1, 0}};

    public void solve(char[][] board) {
        int m = board.length, n = board[0].length;

        UnionFind unionFind = new UnionFind(m * n + 1);

        int dummy = m * n;

        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') {
                unionFind.union(getIndex(n, 0, j), dummy);
            }
            if (board[m - 1][j] == 'O') {
                unionFind.union(getIndex(n, m - 1, j), dummy);
            }
        }
        for (int i = 1; i < m - 1; i++) {
            if (board[i][0] == 'O') {
                unionFind.union(getIndex(n, i, 0), dummy);
            }
            if (board[i][n - 1] == 'O') {
                unionFind.union(getIndex(n, i, n - 1), dummy);
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    for (int[] direction : DIRECTIONS) {
                        int nextI = i + direction[0];
                        int nextJ = j + direction[1];
                        if (nextI < m && nextJ < n && board[nextI][nextJ] == 'O') {
                            unionFind.union(getIndex(n, i, j), getIndex(n, nextI, nextJ));
                        }
                    }
                }
            }
        }

        for (int i = 1; i < m - 1; i++) {
            for (int j = 1; j < n - 1; j++) {
                if (board[i][j] == 'O' && !unionFind.isConnected(getIndex(n, i, j), dummy)) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private int getIndex(int width, int i, int j) {
        return i * width + j;
    }
}
Reference

130. Surrounded Regions