749. Contain Virus.cpp
Code\n\nclass Solution {\npublic:\n    int containVirus(vector<vector<int>>& grid) {\n        int ans = 0;\n        while (true) {\n            int walls = mode
**Code**\n```\nclass Solution {\npublic:\n    int containVirus(vector<vector<int>>& grid) {\n        int ans = 0;\n        while (true) {\n            int walls = model(grid);\n            if (walls == 0) break;\n            ans += walls;\n        }\n        return ans;\n    }\nprivate:\n    int model(vector<vector<int>>& grid) {\n        int m = grid.size(), n = grid[0].size(), N = 100;\n        vector<unordered_set<int>> virus, toInfect;\n        vector<vector<int>> visited(m, vector<int>(n, 0));\n        vector<int> walls;\n        for (int i = 0; i < m; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid[i][j] == 1 && visited[i][j] == 0) {\n                    virus.push_back(unordered_set<int>());\n                    toInfect.push_back(unordered_set<int>());\n                    walls.push_back(0);\n                    dfs(grid, visited, virus.back(), toInfect.back(), walls.back(), i, j);\n                }\n            }\n        }\n        int maxArea = 0, idx = -1;\n        for (int i = 0; i < toInfect.size(); i++) {\n            if (toInfect[i].size() > maxArea) {\n                maxArea = toInfect[i].size();\n                idx = i;\n            }\n        }\n        if (idx == -1) return 0;\n        for (int i = 0; i < toInfect.size(); i++) {\n            if (i != idx) {\n                for (int key : toInfect[i]) \n                    grid[key/N][key%N] = 1;\n            }\n            else {\n                for (int key: virus[i]) \n                    grid[key/N][key%N] = -1;\n            }\n        }\n        return walls[idx];\n    }\nprivate:\n    void dfs(vector<vector<int>>& grid, vector<vector<int>>& visited, unordered_set<int>& virus, unordered_set<int>& toInfect, int& wall, int row, int col) {\n        int m = grid.size(), n = grid[0].size(), N = 100;\n        if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col] == 1) return;\n        if (grid[row][col] == 1) {\n            visited[row][col] = 1;\n            virus.insert(row*N + col);\n            vector<int> dir = {0, -1, 0, 1, 0};\n            for (int i = 0; i < 4; i++)\n                dfs(grid, visited, virus, toInfect, wall, row+dir[i], col+dir[i+1]);\n        }\n        else if (grid[row][col] == 0) {\n            wall++;\n            toInfect.insert(row*N + col);\n        }\n    }\n};\n```
['C']