130. Surrounded Regions

![https://leetcode.com/problems/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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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

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.

  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
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
class Solution {
    int[][] DIRECTIONS = new int[][] {
        {1, 0},
        {-1, 0},
        {0, -1},
        {0, 1}
    };
    /*
    [
    ["X","O","X","O","X","O"],
    ["O","X","O","X","O","X"],
    ["X","O","X","O","X","O"],
    ["O","X","O","X","O","X"]
    
    ]
    
    [
    ["O","X","X","O","X"],
    ["X","O","O","X","O"],
    ["X","O","X","O","X"],
    ["O","X","O","O","O"],
    ["X","X","O","X","O"]
    ]
    
    [
    ["X","O","X","X"],
    ["O","X","O","X"],
    ["X","O","X","O"],
    ["O","X","O","X"],
    ["X","O","X","O"],
    ["O","X","O","X"]
    ]
    
    */
    int n,m;
    public void solve(char[][] board) {
        n = board.length;
        
        if (n == 0) {
            return;
        }
        
        m = board[0].length;
        UF uf = new UF(n * m);
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O') {
                    for (int[] dir: DIRECTIONS) {
                        int row = dir[0] + i;
                        int col = dir[1] + j;
                        if (row >= 0 && row < n && col >= 0 && col < m 
                            && board[row][col] == 'O') {
                            uf.union(getIndex(i, j), getIndex(row, col));
                            // System.out.printf("union %d,%d and %d,%d %n", i, j, row, col);
                        }
                    }
                }
            }
        }
        
        Set<Integer> remains = new HashSet<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O' && 
                    // is boarder
                    (i == 0 || i == n - 1 || j == 0 || j == m - 1)) {
                    remains.add(uf.find(getIndex(i, j)));
                }  
            }
        }
        
        // System.out.println(remains);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == 'O' && !remains.contains(uf.find(getIndex(i, j)))) {
                    board[i][j] = 'X';
                }
            }
        }                
    }
    
    int getIndex(int i , int j) {
        int index = i * m + j;
        // System.out.printf("%d, %d to index %d %n", i, j, index);
        return index;
    }
    
    static class UF {
        
        int[] a;
        int[] sz;
        
        public UF(int n) {
            this.a = new int[n];
            this.sz = new int[n];
            
            for (int i = 0; i < n; i++) {
                this.a[i] = i;
                this.sz[i] = 1;
            }
        }
        
        int find(int p) {
            while (p != a[p]) {
                p = a[p];
            }
            return p;
        }
        
        void union(int p, int q) {
            int parentP = find(p);
            int parentQ = find(q);
            if (sz[parentP] > sz[parentQ]) {
                a[parentQ] = parentP;
                sz[parentP] += sz[parentQ]; 
            } else {
                a[parentP] = parentQ;
                sz[parentQ] += sz[parentP]; 
            }
        }
    }
}