C++ Solution which is easy to understand
Intuition\n The objective is to identify the region that affects the maximum   number of blocks and construct walls around it. This process is repeated until th
# Intuition\n The objective is to identify the region that affects the maximum   number of blocks and construct walls around it. This process is repeated until there are no remaining open regions\n\n# Approach\n\n1. find region which impacts maximum blocks\n2. contruct walls around it and deidentify the region and add walls to the ans.\n3. spread contamination to 1 neighbour blocks for each region present with virus\n4. repat step 1 until there  is no region left\n\n\n\n\n\n# Code\n```\nclass Solution {\npublic:\n    int containVirus(vector<vector<int>>& inf) {\n\n \n        int m  = inf.size();\n        int n = inf[0].size();\n        int ans = FindWalls(m,n,inf);  \n        return ans;    \n\n    }\n\n    int FindWalls(int m , int n , vector<vector<int>>& inf)\n    {\n       \n         int ans = 0;\n         int maxima = 0 ;\n         int start_x = 0;\n         int start_y = 0;\n         \n         while(true)\n         {\n            maxima = 0;\n            int local_ans = 0;\n            vector<vector<int>> v(m,vector<int>(n,0));\n            for(int i = 0 ; i< m;i++)\n            {\n                for(int j = 0 ;j<n;j++)\n                {\n                      \n                   \n                    if(inf[i][j]==1&&v[i][j]==0)\n                    {\n                        initialize(v,m,n,inf);\n                        local_ans = blocks(i,j,v,inf,m,n);\n                        if(local_ans>maxima)\n                        {\n                            start_x = i;\n                            start_y = j;\n                        }\n                        maxima = max(maxima,local_ans);\n                    }\n\n                }\n\n             }\n\n             if(maxima == 0)\n                return ans;\n            \n            for(int i = 0 ;i<m;i++)\n                for(int j =0 ; j<n;j++)\n                    v[i][j]=0;\n            ans+=blockToSpread(start_x,start_y,v,inf,m,n);\n            vector<vector<int>> G(m,vector<int>(n,0));\n            Dismantle(start_x,start_y,inf,G,m,n);\n            ContaminateMarking(inf,m,n);   \n            Contaminate(inf,m,n);     \n         }\n    }\n\n  \nvoid initialize(vector<vector<int>>& v, int m , int n,vector<vector<int>>& inf)\n    {\n        for(int i = 0 ;i<m;i++)\n        {\n            for(int j = 0 ; j<n;j++)\n            {\n                if(inf[i][j]==0)\n                    v[i][j]=0;\n            }\n        }\n    }\n\n   int blocks(int x, int y,vector<vector<int>>& v,  vector<vector<int>>& inf , int m , int n)\n    {\n          if(x<0||x>=m||y<0||y>=n)\n            return 0 ;\n            \n           \n\n            if(v[x][y]==1)\n                return 0;\n\n            v[x][y] = 1;\n            \n            if(inf[x][y]==0)\n                return 1;\n            if(inf[x][y]==-1)\n                return 0; \n\n\n            int sum = 0 ;\n            if(inf[x][y]==1)\n            {\n                sum+=blocks(x+1,y,v,inf,m,n);\n                sum+=blocks(x-1,y,v,inf,m,n);\n                sum+=blocks(x,y-1,v,inf,m,n);\n                sum+=blocks(x,y+1,v,inf,m,n);\n            }\n            return sum;\n\n\n    }\n\n    int blockToSpread(int x, int y,vector<vector<int>>& v,  vector<vector<int>>& inf , int m , int n)\n    {\n          if(x<0||x>=m||y<0||y>=n)\n            return 0 ;\n            \n             if(inf[x][y]==0)\n                {\n                 return 1;\n                }\n\n            if(v[x][y]==1)\n                return 0;\n\n            v[x][y] = 1;\n            \n            int sum = 0 ;\n            if(inf[x][y]==1)\n            {\n                sum+=blockToSpread(x+1,y,v,inf,m,n);\n                sum+=blockToSpread(x-1,y,v,inf,m,n);\n                sum+=blockToSpread(x,y-1,v,inf,m,n);\n                sum+=blockToSpread(x,y+1,v,inf,m,n);\n            }\n            return sum;\n\n\n    }\n\n\n    void Dismantle(int x, int y, vector<vector<int>>& inf , vector<vector<int>>& G , int  m, int n)\n    {\n        if(x<0||x>=m||y<0||y>=n)\n            return;\n\n        if(G[x][y]==1)\n            return;\n\n        G[x][y]=1;\n\n        if(inf[x][y]==1)\n        {\n            inf[x][y]=-1;\n            Dismantle(x+1,y,inf,G,m,n);\n            Dismantle(x-1,y,inf,G,m,n);\n            Dismantle(x,y+1,inf,G,m,n);\n            Dismantle(x,y-1,inf,G,m,n);\n\n        }\n        else\n        {\n            return;\n        }\n                    \n    }\n\n    void ContaminateMarking(vector<vector<int>>& inf , int m , int n)\n    {\n        \n\n        for(int i  = 0 ;i<m;i++)\n           {\n               for(int j = 0 ; j<n;j++)\n                {\n                    if(inf[i][j]==1)\n                        {\n                            ContaminateBlockMarking(i+1,j,inf,m,n);\n                            ContaminateBlockMarking(i-1,j,inf,m,n);\n                            ContaminateBlockMarking(i,j+1,inf,m,n);\n                            ContaminateBlockMarking(i,j-1,inf,m,n);\n                        }\n                }\n           }\n        \n       \n        return;\n\n    }\n\n     void ContaminateBlockMarking(int x , int y , vector<vector<int>>& inf, int m ,int  n )\n    {\n          if(x<0||x>=m||y<0||y>=n)\n            return;\n           \n          if(inf[x][y] == 0)\n            inf[x][y] = -2;\n\n        return;\n\n    }\n\n    void Contaminate(vector<vector<int>>& inf , int m , int n)\n    {\n           for(int i  = 0 ;i<m;i++)\n           {\n               for(int j = 0 ; j<n;j++)\n                {\n                    if(inf[i][j]==-2)\n                        inf[i][j]= 1;\n                }\n           }\n           return;\n    }\n\n};\n```
['Greedy', 'Depth-First Search', 'C++']