DFS
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int containVirus(vector<vector<int>>& a) {\n        int m = a.size();\n        int n = a[0].size();\n        \n        vector<vector<int>> dir = {{0,1},{0,-1},{-1,0},{1,0}};\n        vector<bool> vs(m*n, false);\n        unordered_map<int, vector<int>> vregion; // virus region\n\n        /* using set decide priority by size of set without duplocated*/\n        unordered_map<int, set<int>> uregion;  // uninfected region\n        unordered_map<int, int> count;    // count for uninfected region\n\n        int un_region = 0;\n        int virus_region = 0;\n        // get all virus ans neighbour region;\n        function<void(int)> dfs = [&](int p) {\n            vregion[virus_region].push_back(p);\n            vs[p] = true;\n            for (auto& d : dir) {\n                int nx = p/n + d[0];\n                int ny = p%n + d[1];\n                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;\n                if (a[nx][ny] == 0) {\n                    uregion[un_region].insert(nx*n + ny);\n                    count[un_region]++;\n                }\n                if (a[nx][ny] == 1 && !vs[nx*n + ny]) dfs(nx*n + ny);\n\n            }\n        };\n        function<void()> calculate_region = [&] () {\n            un_region = 0;\n            virus_region = 0;\n            vregion.clear(); uregion.clear(); count.clear();\n            for (int i = 0; i < m; i++) {\n                for (int j = 0; j < n; j++) {\n                    if (a[i][j] == 1 && !vs[i*n+j]) {\n                        dfs(i*n+j);\n                        un_region++;\n                        virus_region++;\n                    }\n                }\n            }\n        };\n        int ans= 0;\n        while (true) {\n            for (int i = 0; i < m*n; i++) vs[i] = false;\n            calculate_region();\n            if (vregion.size() ==0) break;\n            int umax_region =  0;\n            int max_num = -1;\n            for (auto& m : uregion) {\n                int sz = m.second.size();\n                if (sz > max_num) {\n                    max_num = sz;\n                    umax_region = m.first;\n                }\n            }\n            ans += count[umax_region];\n            // change quarantine region to -1;\n            for (auto& x : vregion[umax_region]) {\n                a[x/n][x%n] = -1;\n            }\n            // spread virus all other region;\n            for (auto&m : uregion) {\n                if (m.first == umax_region) continue;\n                for (auto& x : m.second) a[x/n][x%n] = 1;\n            }\n        }\n        return ans;\n    }\n};\n```
['Depth-First Search', 'C++']