Java Union Find Solution. Simulate the evolution.
Just provide another way to solve the problem. Although the code is lengthy, but the idea is simple and commented inline. \n\nclass Solution {\n    public int c
Just provide another way to solve the problem. Although the code is lengthy, but the idea is simple and commented inline. \n```\nclass Solution {\n    public int containVirus(int[][] grid) {\n        int rst = 0;\n        int s = solve(grid);\n        while (s != 0) {\n            rst += s;\n            s = solve(grid);\n        }\n        return rst;\n    }\n\n    private int solve(int[][] g) {\n        int r = g.length;\n        int c = g[0].length;\n        int[] uf = new int[getIdx(g, r - 1, c - 1) + 1];\n        initUF(uf);\n        int[][] dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};\n        // First mark connected components into same group.\n        for (int i = 0; i < r; ++i) {\n            for (int j = 0; j < c; ++j) {\n                if (g[i][j] <= 0) {\n                    continue;\n                }\n                for (int k = 0; k < 4; ++k) {\n                    int x = i + dir[k][0];\n                    int y = j + dir[k][1];\n                    if (x >= 0 && x < r && y >= 0 && y < c && g[x][y] > 0) {\n                        union(uf, getIdx(g, x, y), getIdx(g, i, j));\n                    }\n                }\n            }\n        }\n        // blankSets, key is group index, value set contains all adjacent 0s.\n        Map<Integer, Set<Integer>> blankSets = new HashMap<>();\n        // wallCounts, key is group index, value is count of walls to build.\n        Map<Integer, Integer> wallCounts = new HashMap<>();\n        // And then iterate graph, count adjacent 0s and walls to build.\n        for (int i = 0; i < r; ++i) {\n            for (int j = 0; j < c; ++j) {\n                if (g[i][j] <= 0) {\n                    continue;\n                }\n                int idx = find(uf, getIdx(g, i, j));\n                if (!blankSets.containsKey(idx)) {\n                    blankSets.put(idx, new HashSet<>());\n                }\n                for (int k = 0; k < 4; ++k) {\n                    int x = i + dir[k][0];\n                    int y = j + dir[k][1];\n                    if (x >= 0 && x < r && y >= 0 && y < c && g[x][y] == 0) {\n                        int blankIdx = getIdx(g, x, y);\n                        blankSets.get(idx).add(blankIdx);\n                        wallCounts.put(idx, wallCounts.getOrDefault(idx, 0) + 1);\n                    }\n                }\n            }\n        }\n        // And then find the connected component with max adjacent 0s.\n        int maxIdx = 0;\n        int maxSize = 0;\n        int walls = 0;\n        for (int idx : blankSets.keySet()) {\n            Set<Integer> s = blankSets.get(idx);\n            if (s.size() > maxSize) {\n                maxSize = s.size();\n                maxIdx = idx;\n                walls = wallCounts.get(idx);\n            }\n        }\n        if (maxSize == 0) {\n            return 0;\n        }\n        // And finally, update the graph in-place, mark contained virus to be -1, \n        // and spread other virus to adjacent 0s.\n        int[][] tmp = cp(g);\n        for (int i = 0; i < r; ++i) {\n            for (int j = 0; j < c; ++j) {\n                if (tmp[i][j] <= 0) {\n                    continue;\n                }\n                int idx = find(uf, getIdx(g, i, j));\n                if (idx == maxIdx) {\n                    g[i][j] = -1;\n                    continue;\n                }\n                for (int k = 0; k < 4; ++k) {\n                    int x = i + dir[k][0];\n                    int y = j + dir[k][1];\n                    if (x >= 0 && x < r && y >= 0 && y < c && tmp[x][y] == 0) {\n                        g[x][y] = 1;\n                    }\n                }\n            }\n        }\n        return walls;\n    }\n\n    // 2d to 1d index mapping.\n    private int getIdx(int[][] g, int x, int y) {\n        return g[0].length * x + y;\n    }\n\n    // methods for union find set.\n    private void initUF(int[] uf) {\n        for (int i = 0; i < uf.length; ++i) {\n            uf[i] = i;\n        }\n    }\n\n    private int find(int[] uf, int a) {\n        if (uf[a] == a) {\n            return a;\n        }\n        int r = find(uf, uf[a]);\n        uf[a] = r;\n        return r;\n    }\n\n    private void union(int[] uf, int a, int b) {\n        int ga = find(uf, a);\n        int gb = find(uf, b);\n        uf[gb] = ga;\n    }\n\n    private int[][] cp(int[][] g) {\n        int[][] r = new int[g.length][g[0].length];\n        for (int i = 0; i < g.length; ++i) {\n            for (int j = 0; j < g[0].length; ++j) {\n                r[i][j] = g[i][j];\n            }\n        }\n        return r;\n    }\n}\n```
[]