C++ | dfs
Complexity\n- Time complexity: O((m * n)^2)\n\n- Space complexity: O(m * n)\n\n# Code\ncpp []\nclass Solution {\n    struct RegionInfo {\n        std::set<std::
# Complexity\n- Time complexity: O((m * n)^2)\n\n- Space complexity: O(m * n)\n\n# Code\n```cpp []\nclass Solution {\n    struct RegionInfo {\n        std::set<std::pair<int, int>> threat;\n        std::set<std::pair<int, int>> infectedCells;\n        int wallsNeeded;\n        RegionInfo() : wallsNeeded(0) {}\n    };\n\n    static constexpr std::array<int, 5> directions = {0, 1, 0, -1, 0};\n    int m, n;\n\n    void dfs(int i, int j, vector<vector<int>> &isInfected, vector<vector<bool>> &visited, RegionInfo &region) {\n        visited[i][j] = true;\n        region.infectedCells.emplace(i, j);\n\n        for (int d = 0; d < 4; ++d) {\n            int nextI = i + directions[d];\n            int nextJ = j + directions[d + 1];\n\n            if (nextI < 0 || nextI >= m || nextJ < 0 || nextJ >= n) {\n                continue;\n            }\n            \n            if (isInfected[nextI][nextJ] == 0) {\n                region.threat.emplace(nextI, nextJ);\n                ++region.wallsNeeded;\n            } else if (isInfected[nextI][nextJ] == 1 && !visited[nextI][nextJ]) {\n                dfs(nextI, nextJ, isInfected, visited, region);\n            }\n        }\n    }\n\npublic:\n    int containVirus(vector<vector<int>>& isInfected) {\n        m = isInfected.size();\n        n = isInfected[0].size();\n        int totalWalls = 0;\n\n        while (true) {\n            std::vector<RegionInfo> regions;\n            std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));\n\n            for (int i = 0; i < m; ++i) {\n                for (int j = 0; j < n; ++j) {\n                    if (isInfected[i][j] == 1 && !visited[i][j]) {\n                        RegionInfo region;\n\n                        dfs(i, j, isInfected, visited, region);\n\n                        if (!region.threat.empty()) {\n                            regions.push_back(region);\n                        }\n                    }\n                }\n            }\n\n            if (regions.empty()) {\n                break;\n            }\n\n            auto maxThreatRegion = std::max_element(regions.begin(), regions.end(),\n                [](const RegionInfo &a, const RegionInfo &b) {\n                    return a.threat.size() < b.threat.size();\n                }\n            );\n\n            totalWalls += maxThreatRegion->wallsNeeded;\n\n            for (const auto &[i, j] : maxThreatRegion->infectedCells) {\n                isInfected[i][j] = -1;\n            }\n\n            for (int k = 0; k < regions.size(); ++k) {\n                if (&regions[k] == &(*maxThreatRegion)) {\n                    continue;\n                }\n                for (const auto &[i, j] : regions[k].infectedCells) {\n                    for (int d = 0; d < 4; ++d) {\n                        int nextI = i + directions[d];\n                        int nextJ = j + directions[d + 1];\n                        if (nextI >= 0 && nextI < m && nextJ >= 0 && nextJ < n && isInfected[nextI][nextJ] == 0) {\n                            isInfected[nextI][nextJ] = 1;\n                        }\n                    }\n                }\n            }\n        }\n\n        return totalWalls;\n    }\n};\n\n```
['Depth-First Search', 'Graph', 'Recursion', 'Matrix', 'C++']