surrounded-regions.java

import java.util.*;

public class Solution {
    class UnionFind {
        HashMap<Integer, Integer> father;

        UnionFind(int n) {
            this.father = new HashMap<Integer, Integer>(n);
            for (int i = 0; i < n; i++) {
                father.put(i, i);
            }
            father.put(-100, -100);

        }

        int find(int x) {
            int parent = father.get(x);
            while (parent != father.get(parent)) {
                parent = father.get(parent);
            }
            return parent;
        }

        int compressed_find(int x) {
            //  System.out.println(x+" +  "+father.get(x));
            int parent = father.get(x);
            while (parent != father.get(parent)) {
                parent = father.get(parent);
            }
            int temp = -1;
            int fa = father.get(x);
            while (fa != father.get(fa)) {
                temp = father.get(fa);
                father.put(fa, parent);
                fa = temp;
            }
            return parent;

        }

        void union(int x, int y) {
            int fa_x = find(x);
            int fa_y = find(y);

            if (fa_x != fa_y)
                father.put(fa_x, fa_y);
        }
    }

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

        int rows = board.length;
        if (rows == 0)
            return;
        int cols = board[0].length;
        if (cols == 0)
            return;
        if ((rows + cols) == 2)
            return;
        UnionFind uf = new UnionFind(cols * rows);

        int oRoot = -100;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'X') continue;
                int curr = i * cols + j;
                if (i == 0 || i == rows - 1 || j == 0 || j == cols - 1) {
                    uf.union(curr, oRoot);
                } else {
                    if (j + 1 < cols && board[i][j + 1] == 'O')
                        uf.union(curr, i * cols + j + 1);
                    if (j - 1 >= 0 && board[i][j - 1] == 'O')
                        uf.union(curr, i * cols + j - 1);
                    if (i + 1 < rows && board[i + 1][j] == 'O')
                        uf.union(curr, (i + 1) * cols + j);
                    if (i - 1 >= 0 && board[i - 1][j] == 'O')
                        uf.union(curr, (i - 1) * cols + j);
                }
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (board[i][j] == 'O' && uf.find(i * cols + j) != oRoot) {
                    board[i][j] = 'X';
                }
            }
        }

        System.out.println(uf.compressed_find(oRoot));

    }

    public static void main(String[] args) {
        Solution s1 = new Solution();

//        char[][] xx = {
//                "OXXOX".toCharArray(),
//                "XOOXO".toCharArray(),
//                "XOXOX".toCharArray(),
//                "OXOOO".toCharArray(),
//                "XXOXO".toCharArray(),
//        };
        char[][] xx2 = {
                "OOO".toCharArray(),
                "OOO".toCharArray(),
                "OOO".toCharArray(),

        };
        s1.solve(xx2);

        // ["OXXOX","XXXXO","XXXOX","OXOOO","XXOXO"]

        for (char[] x : xx2
                ) {
            for (char k : x) {
                System.out.print(k);
            }
            System.out.println();
        }
    }
}