Concise solution, no index tracking (detailed explanation with illustration)
The idea is to find all infected regions and identify the most dangerous one (i.e., infecting most uninfected cells), then update all regions by the rule and re
The idea is to find all infected regions and identify the most dangerous one (i.e., infecting most uninfected cells), then update all regions by the rule and repeat this process until no more infected regions found.\n\nTo accomplish this algorithm, it is useful to define structure `Region` as\n```cpp\n    struct Region {\n        unordered_set<int*> inner, border;\n        size_t perimeter = 0;\n    };\n```\nwhere \n* `inner`: reference to values of inner infected cells \n* `border`: reference to values of *uninfected* cells surrounding inner cells\n* `perimeter`: count of edges between `inner` and `border`\n![0_1513704710688_Region.jpg](/assets/uploads/files/1513704708943-region.jpg) \n**NOTE:** Define `inner` and `border` as value references instead of tracking `(i,j)` indices to save space and avoid copies.\n\n**Algorithm Outline:**\n1. For each day, scan entire grid to find all infected regions `regions` and the max count of `border`. This could be accomplished by either DFS or BFS.\n1. if `regions` is empty, quit; \notherwise,\n   * for the most dangerous region `r`, set `r.inner` to value `-1` (i.e., quarantined);\n   * for other regions `r`, set `r.border` to value `1` (i.e., infected), and accumulate `r.perimeter` (i.e., build new walls)  \n\n```cpp        \n    int containVirus(vector<vector<int>>& grid) \n    {                            \n        for (size_t walls = 0, maxborder = 0; true; )\n        {       \n            // find all infected regions\n            auto regions = findRegions(grid, maxborder);             \n            if (regions.empty()) return walls; // no more infection\n            \n            // update all regions\n            for (auto& r : regions)\n                if (r.border.size() != maxborder) { // infected\n                    for (auto& cell : r.inner) *cell = 1;\n                    for (auto& cell : r.border) *cell = 1;\n                }\n                else walls += r.perimeter; // quarantined\n        }        \n    }    \n```\nDFS routine to explore a region starting at cell `(i,j)`:\n```cpp    \n    void dfs(vector<vector<int>>& grid, int i, int j, Region& r) \n    {\n        // no need to explore if already quarantined\n        if (min(i,j)<0 || i>=grid.size() || j>=grid[0].size() || grid[i][j]<0) return;\n        \n        if (grid[i][j]) { // infected\n            r.inner.insert(&(grid[i][j]=-1));\n            dfs(grid,i+1,j,r), dfs(grid,i,j+1,r), dfs(grid,i-1,j,r), dfs(grid,i,j-1,r);\n        } // border found\n        else r.border.insert(&grid[i][j]), ++r.perimeter;      \n    };    \n```\nFind all infected regions and get max border:\n```cpp    \n    vector<Region> findRegions(vector<vector<int>>& grid, size_t& maxborder) \n    {\n        vector<Region> regions; maxborder = 0;\n        for (int i = 0; i < grid.size(); ++i)\n            for (int j = 0; j < grid[0].size(); ++j)\n                if (grid[i][j] == 1) {\n                    Region r; dfs(grid, i, j, r);\n                    regions.push_back(r);       \n                    maxborder = max(maxborder, r.border.size());\n                }     \n        return regions;\n    }\n```
['Depth-First Search', 'C++']