Easiest Solution
\n\n# Code\njava []\nclass Solution {\n    \n    private static final int[][] DIR = new int[][]{\n        {1, 0}, {-1, 0}, {0, 1}, {0, -1}\n    };\n    \n    pu
\n\n# Code\n``` java []\nclass Solution {\n    \n    private static final int[][] DIR = new int[][]{\n        {1, 0}, {-1, 0}, {0, 1}, {0, -1}\n    };\n    \n    public int containVirus(int[][] isInfected) {\n        int m = isInfected.length, n = isInfected[0].length;\n        int ans = 0;\n        \n        while( true ) {\n            // infected regions, sorted desc according to the number of nearby \n            // uninfected nodes\n            PriorityQueue<Region> pq = new PriorityQueue<Region>();\n            // already visited cells\n            boolean[][] visited = new boolean[m][n];\n            \n            // find regions\n            for(int i=0; i<m; i++) {\n                for(int j=0; j<n; j++) {\n                    \n                    // if current cell is infected, and it\'s not visited\n                    if( isInfected[i][j] != 1 || visited[i][j] ) \n                        continue;\n                    \n                    // we found a new region, dfs to find all the infected\n                    // and uninfected cells in the current region\n                    Region reg = new Region();\n                    dfs(i, j, reg, isInfected, visited, new boolean[m][n], m, n);\n                    \n                    // if there are some uninfected nodes in this region, \n                    // we can contain it, so add it to priority queue\n                    if( reg.uninfected.size() != 0)\n                        pq.offer(reg);\n                }\n            }\n            \n            // if there are no regions to contain, break\n            if( pq.isEmpty() )\n                break;\n\n            // Contain region with most uninfected nodes\n            Region containReg = pq.poll();\n            ans += containReg.wallsRequired;\n            \n            // use (2) to mark a cell as contained\n            for(int[] cell : containReg.infected)\n                isInfected[cell[0]][cell[1]] = 2;\n            \n            // Spread infection to uninfected nodes in other regions\n            while( !pq.isEmpty() ) {\n                Region spreadReg = pq.poll();\n                \n                for(int[] cell : spreadReg.uninfected)\n                    isInfected[cell[0]][cell[1]] = 1;\n            }\n        }\n        return ans;\n    }\n    \n    private void dfs(int i, int j, Region reg, int[][] grid, boolean[][] visited, boolean[][] uninfectedVis, int m, int n) {\n        visited[i][j] = true;\n        reg.addInfected(i, j);\n        \n        for(int[] dir : DIR) {\n            int di = i + dir[0];\n            int dj = j + dir[1];\n            \n            // continue, if out of bounds OR contained OR already visited\n            if( di < 0 || dj < 0 || di == m || dj == n || grid[di][dj] == 2 || visited[di][dj] )\n                continue;\n            \n            // if neighbour node is not infected\n            if( grid[di][dj] == 0 ) {\n                // a wall will require to stop the spread from cell (i,j) to (di, dj)\n                reg.wallsRequired++;\n                \n                // if this uninfected node is not already visited for current region\n                if( !uninfectedVis[di][dj] ) {\n                    uninfectedVis[di][dj] = true;\n                    reg.addUninfected(di, dj);\n                }\n            } else \n                dfs(di, dj, reg, grid, visited, uninfectedVis, m, n);\n        }\n    }\n}\nclass Region implements Comparable<Region> {\n    public List<int[]> infected;\n    public List<int[]> uninfected;\n    public int wallsRequired;\n    \n    public Region() {\n        infected = new ArrayList();\n        uninfected = new ArrayList();\n    }\n    \n    public void addInfected(int row, int col) {\n        infected.add(new int[]{ row, col });\n    }\n    \n    public void addUninfected(int row, int col) {\n        uninfected.add(new int[]{ row, col });\n    }\n    \n    @Override\n    public int compareTo(Region r2) {\n        return Integer.compare(r2.uninfected.size(), uninfected.size());\n    }\n}\n```\n```c++ []\nclass Solution {\npublic:\n    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};\n    int walls=0;\n    \n    bool isValid(int i,int j,int m,int n,vector<vector<int>> &vis)\n    {\n        return (i>=0 && i<m && j>=0 && j<n && !vis[i][j]); \n    }\n    \n    int find(int i,int j,int m,int n,vector<vector<int>>& a)\n    {\n        int c=0;\n        \n        queue<pair<int,int>> q;\n        vector<vector<int>> vis(m,vector<int>(n,0));\n        \n        a[i][j]=2;\n        q.push({i,j});\n        \n        while(!q.empty())\n        {\n            i=q.front().first;\n            j=q.front().second;\n            q.pop();\n            \n            for(int k=0;k<4;k++)\n            {\n                if(isValid(i+dx[k],j+dy[k],m,n,vis))\n                {\n                    if(a[i+dx[k]][j+dy[k]]==0)\n                        c++;\n                    else if(a[i+dx[k]][j+dy[k]]==1)\n                    {\n                        a[i+dx[k]][j+dy[k]]=2;\n                        q.push({i+dx[k],j+dy[k]});\n                    }\n                                            \n                    vis[i+dx[k]][j+dy[k]]=1;\n                    \n                }\n            }\n        }\n        \n        return c;\n    }\n    \n    void putwalls(pair<int,int> &change,int m,int n,vector<vector<int>>& a)\n    {\n        int i,j;\n        i=change.first;\n        j=change.second;\n        \n        queue<pair<int,int>> q;\n        vector<vector<int>> vis(m,vector<int>(n,0));\n        \n        q.push({i,j});\n        \n        while(!q.empty())\n        {\n            i=q.front().first;\n            j=q.front().second;\n            a[i][j]=-1;\n            q.pop();\n            \n            \n            for(int k=0;k<4;k++)\n            {\n                if(isValid(i+dx[k],j+dy[k],m,n,vis))\n                {\n                    if(a[i+dx[k]][j+dy[k]]==2)\n                    {\n                        q.push({i+dx[k],j+dy[k]});\n                        a[i+dx[k]][j+dy[k]]=-1;\n                        vis[i+dx[k]][j+dy[k]]=1;    \n                    } \n                    else if(a[i+dx[k]][j+dy[k]]==0)\n                        walls++;\n                }\n            }\n        }\n    }\n    \n    void spread(int m,int n,vector<vector<int>>& a)\n    {\n        int i,j;\n        queue<pair<int,int>> q;\n        vector<vector<int>> vis(m,vector<int>(n,0));\n        \n        for(i=0;i<m;i++)\n        {\n            for(j=0;j<n;j++)\n            {\n                if(a[i][j]==2)\n                {\n                    a[i][j]=1;\n                    q.push({i,j});\n\n                }\n            }\n        }\n        \n        while(!q.empty())\n        {\n            i=q.front().first;\n            j=q.front().second;\n            q.pop();\n            \n            for(int k=0;k<4;k++)\n            {\n                if(isValid(i+dx[k],j+dy[k],m,n,vis) && a[i+dx[k]][j+dy[k]]==0)\n                {\n                    a[i+dx[k]][j+dy[k]]=1;\n                    vis[i+dx[k]][j+dy[k]]=1;     \n                }\n            }\n        }\n    }\n    \n    int containVirus(vector<vector<int>>& a) {\n        int m=a.size(),n=a[0].size();\n        int i,j;\n        \n        int infected=INT_MIN;\n        pair<int,int> change;\n        \n        while(infected!=0)\n        {\n            infected=0;\n            for(i=0;i<m;i++)\n            {\n                for(j=0;j<n;j++)\n                {\n                    if(a[i][j]==1)\n                    {\n                        int x=find(i,j,m,n,a);\n                        if(x>infected)\n                        {\n                            change={i,j};\n                            infected=x;\n                        }\n                    }\n                }\n            }\n            \n            if(infected!=0)\n            {\n                putwalls(change,m,n,a);\n                spread(m,n,a);\n            }\n        }\n        \n        return walls;\n    }\n};\n```\n```python3 []\nclass Solution:\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        \'\'\'\n        isInfected[r][c]:\n            0 : Uninfected\n            1 : Infected\n            2 : Infected & restricted\n        \'\'\'\n        m = len(isInfected)\n        n = len(isInfected[0])\n\n        borders = 0\n        threatened = 0\n        def dfs(r, c, id):\n            nonlocal borders, threatened\n            if r < 0 or r>=m or c < 0 or c>=n:\n                return\n\n            if isInfected[r][c] == 1:\n                if visited[r][c] == 0:\n                    visited[r][c] = 1\n                    dfs(r-1, c, id)\n                    dfs(r+1, c, id)\n                    dfs(r, c-1, id)\n                    dfs(r, c+1, id)\n                else:\n                    pass\n            elif isInfected[r][c] == 0:\n                if visited[r][c] == id:\n                    borders += 1\n                else:\n                    borders += 1\n                    threatened += 1\n                    visited[r][c] = id\n        \n        def flood(r, c, find, repl):\n            if r < 0 or r>=m or c < 0 or c>=n or isInfected[r][c] != find:\n                return\n            isInfected[r][c] = repl\n            flood(r-1, c, find, repl)\n            flood(r+1, c, find, repl)\n            flood(r, c-1, find, repl)\n            flood(r, c+1, find, repl)\n        \n        def expand(r, c, id):\n            if r < 0 or r>=m or c < 0 or c>=n or visited[r][c] == 1:\n                return\n            visited[r][c] = 1\n            if isInfected[r][c] == 0:\n                isInfected[r][c] = 1\n            elif isInfected[r][c] == 1:\n                expand(r+1, c, id)\n                expand(r-1, c, id)\n                expand(r, c-1, id)\n                expand(r, c+1, id)   \n\n        total_walls = 0\n\n        while True:\n            # Day ---------------------------------------------------\n            max_th = 0\n            max_th_loc = (None, None)\n            max_th_border = 0\n            id = 3\n            visited = [[0] * n for _ in range(m)]\n\n            for r in range(m):\n                for c in range(n):\n                    if isInfected[r][c]==1 and visited[r][c] == 0:\n                        \n                        borders = 0\n                        threatened = 0\n                        dfs(r, c, id)\n                        id += 1\n                        if threatened > max_th:\n                            max_th = threatened\n                            max_th_loc = r, c\n                            max_th_border = borders\n            \n            if max_th == 0:\n                break\n            total_walls += max_th_border\n            # Restrict bordered region by making them dormant\n            flood(*max_th_loc, 1, 2)\n\n            # Night -------------------------------------------------\n\n            visited = [[0] * n for _ in range(m)]\n            for r in range(m):\n                for c in range(n):\n                    if isInfected[r][c]==1 and visited[r][c] == 0:\n                        expand(r, c, id)\n                        id += 1\n\n        return total_walls\n\n\n\n\n\n```
['C++', 'Java', 'Python3']