[749. Contain Virus] C++_AC_16ms_DFS
Pretty straightforward problem, by using DFS and following the requirements of this problem.\n\n    class Solution {\n    public:\n    int containVirus(vector>&
Pretty straightforward problem, by using DFS and following the requirements of this problem.\n\n    class Solution {\n    public:\n    int containVirus(vector<vector<int>>& grid) {\n        if(grid.empty()) return 0;\n        int m = grid.size();\n        int n = grid[0].size();\n        int res = 0;\n        //The number of rows and columns of grid will each be in the range [1, 50]. i*100 + j as the "index number"\n        while(true){\n            vector<vector<bool>> check(m, vector<bool>(n, false));\n            //for dfs, find the continuous region\n\n            unordered_map<int, unordered_set<int>> cells;\n            // the cells(value = 0) will be affected by the region\n\n            unordered_map<int, int> length;\n            //the length of each region\n            \n            int max_region_id = 0;\n            int max_region_length = 0;\n            int max_region_cells = 0;\n            for(int i = 0; i < m; ++i){\n                for(int j = 0; j < n; ++j){\n                    if(grid[i][j] == 1 && !check[i][j]) {//go into the region search\n                        int id = i * 100 + j;\n                        find_bound(grid, length, check, i, j, m, n, cells, id);\n                        if(length[id]){\n                                if(cells[id].size() > max_region_cells){\n          //if the current region is much more serious\n                                    max_region_cells = cells[id].size();\n                                    max_region_length = length[id];\n                                    max_region_id = id;\n                            }\n                        }\n                    }\n                }\n            }\n            if(max_region_length == 0) break;\n            res += max_region_length;\n            set_wall(grid, max_region_id/100, max_region_id%100, m, n);\n            cells.erase(max_region_id);\n            for(auto v : cells){\n                update(grid, v.second, m, n);\n            }\n        }\n        return res;\n        \n    }\n    void set_wall(vector<vector<int>>& grid, int i, int j, int m, int n){\n        grid[i][j] = -1;\n        if(i-1 >= 0 && grid[i-1][j] == 1) set_wall(grid, i-1, j, m, n);\n        if(i+1 < m && grid[i+1][j] == 1) set_wall(grid, i+1, j, m, n);\n        if(j-1 >= 0 && grid[i][j-1] == 1) set_wall(grid, i, j-1, m, n);\n        if(j+1 < n && grid[i][j+1] == 1) set_wall(grid, i, j+1, m, n);\n    }\n    \n    void find_bound(vector<vector<int>>& grid, unordered_map<int, int>& length, vector<vector<bool>>& check, int i, int j, int m, int n, unordered_map<int, unordered_set<int>>& cells, int id){\n        check[i][j] = true;\n        if(i-1 >= 0 && grid[i-1][j] == 0) {length[id]++; cells[id].insert((i-1)*100 + j);}\n        if(j-1 >= 0 && grid[i][j-1] == 0) {length[id]++; cells[id].insert(i*100 + j-1);}\n        if(i+1 < m && grid[i+1][j] == 0) {length[id]++; cells[id].insert((i+1)*100 + j);}\n        if(j+1 < n && grid[i][j+1] == 0) {length[id]++; cells[id].insert(i*100 + j + 1);}\n        if(i-1 >= 0 && grid[i-1][j] == 1 && !check[i-1][j]) find_bound(grid, length, check, i-1, j, m, n, cells, id);\n        if(j-1 >= 0 && grid[i][j-1] == 1 && !check[i][j-1]) find_bound(grid, length, check, i, j-1, m, n, cells, id);\n        if(i+1 < m && grid[i+1][j] == 1 && !check[i+1][j]) find_bound(grid, length, check, i+1, j, m, n, cells, id);\n        if(j+1 < n && grid[i][j+1] == 1 && !check[i][j+1]) find_bound(grid, length, check, i, j+1, m, n, cells, id);\n    }\n    \n    void update(vector<vector<int>>& grid, unordered_set<int>& bound, int m, int n){\n        for(auto idx : bound){\n            int i = idx/100;\n            int j = idx%100;\n            grid[i][j] = 1;\n        }\n    }\n    };
[]