Simulation with Union-Find (C++, 12ms)
This is a straight forward solution without any algorithmic tricks. I applied union-find here instead of DFS. Code is clear enough to understand. \nC++\nclass S
This is a straight forward solution without any algorithmic tricks. I applied union-find here instead of DFS. Code is clear enough to understand. \n```C++\nclass Solution {\n    int M, N, K;\n    vector<int> root, affect;\n    \n    // operations of Union-Find\n    int find_root(int i) {\n        if (root[i] == -1) return -1;       // -1: this union cannot spread any more\n        if (root[i] == i) return i;\n        root[i] = find_root(root[i]);\n        return root[i];\n    }\n    void union_set(int i, int j) {\n        root[find_root(j)] = find_root(i);\n    }\n    \n    void showGrid(vector<vector<int>>& grid) {\n        for (int i=0; i<M; i++) {\n            for (int j=0; j<N; j++) \n                cout << grid[i][j] << \' \';\n            cout << endl;\n        }\n    }\n    \n    void constructUnions(vector<vector<int>>& grid) {\n        K = M * N;\n        root.resize(K);\n        affect.resize(K, 0);\n        for (int i=0; i<K; i++) {\n            int a = i / N, b = i % N;\n            if (!grid[a][b]) \n                root[i] = -1;\n            else {\n                root[i] = i;\n                if (a && grid[a-1][b] && find_root(i) != find_root(i-N)) union_set(i-N, i);\n                if (b && grid[a][b-1] && find_root(i) != find_root(i-1)) union_set(i-1, i);\n            }\n        }\n        //showGrid(grid);\n    }\n        \n    pair<int, int> findMostAffect(vector<vector<int>>& grid) {\n        fill(affect.begin(), affect.end(), 0);\n        for (int i=0; i<K; i++) {\n            int a = i / N, b = i % N;\n            if (grid[a][b]) continue;\n            unordered_set<int> nei;         // to avoid duplicate adding\n            if (a>0   && grid[a-1][b] && find_root(i-N) != -1) nei.insert(root[i-N]);\n            if (b>0   && grid[a][b-1] && find_root(i-1) != -1) nei.insert(root[i-1]);\n            if (a<M-1 && grid[a+1][b] && find_root(i+N) != -1) nei.insert(root[i+N]);\n            if (b<N-1 && grid[a][b+1] && find_root(i+1) != -1) nei.insert(root[i+1]);\n            for (int n : nei) affect[n] ++;\n        }\n        int maxUnion = -1, mayAffect = 0, maxAffect = 0;\n        for (int r=0; r<K; r++) {\n            if (affect[r] > maxAffect) {\n                maxAffect = affect[r];\n                maxUnion = r;\n            }\n            mayAffect += affect[r];\n        }\n        //cout << "maxUnion:" << maxUnion << ", mayAffect:" << mayAffect << endl;\n        return {maxUnion, mayAffect};\n    }\n        \n    int buildWallAndGrow(vector<vector<int>>& grid, int maxUnion) {\n        int walls = 0;\n        \n        // build walls\n        for (int i=0; i<K; i++) {\n            int a = i / N, b = i % N;\n            if (grid[a][b] && find_root(i) == maxUnion) {\n                if (a>0   && !grid[a-1][b]) walls ++;\n                if (b>0   && !grid[a][b-1]) walls ++;\n                if (a<M-1 && !grid[a+1][b]) walls ++;\n                if (b<N-1 && !grid[a][b+1]) walls ++;\n            }\n        }\n        \n        // disable current union\n        root[maxUnion] = -1;\n        \n        // growth of other unions\n        vector<int> toAffect;\n        for (int i=0; i<K; i++) {\n            int a = i / N, b = i % N;\n            if (!grid[a][b]) {\n                if ((a>0   && grid[a-1][b] && find_root(i-N) != -1) ||\n                    (b>0   && grid[a][b-1] && find_root(i-1) != -1) ||\n                    (a<M-1 && grid[a+1][b] && find_root(i+N) != -1) ||\n                    (b<N-1 && grid[a][b+1] && find_root(i+1) != -1))\n                {\n                    toAffect.push_back(i);\n                }\n            }\n        }\n        for (int i : toAffect) {\n            int a = i / N, b = i % N;\n            root[i] = i;\n            grid[a][b] = 1;\n            if (a>0   && grid[a-1][b] && find_root(i-N) != -1) union_set(i-N, i);\n            if (b>0   && grid[a][b-1] && find_root(i-1) != -1) union_set(i-1, i);\n            if (a<M-1 && grid[a+1][b] && find_root(i+N) != -1) union_set(i+N, i);\n            if (b<N-1 && grid[a][b+1] && find_root(i+1) != -1) union_set(i+1, i);\n        }\n       \n        //cout << "Walls:" << walls << endl;\n        //showGrid(grid);\n        return walls;\n    }\n    \npublic:\n    \n    int containVirus(vector<vector<int>>& grid) {\n        if (!(M = grid.size()) || !(N = grid[0].size())) return 0;\n        constructUnions(grid);\n        \n        int walls = 0;\n        while (true) {\n            auto p = findMostAffect(grid);\n            int maxUnion = p.first;\n            int mayAffect = p.second;\n            \n            if (mayAffect) \n                walls += buildWallAndGrow(grid, maxUnion); \n            else break;\n        }\n        \n        return walls;\n    }\n};\n```
[]