My Neat Java Solution Using Dfs
\nclass Solution {\n    public int containVirus(int[][] grid) {\n        int[] cost = new int[]{0};\n        while(check(grid, cost));\n        return cost[0];\
```\nclass Solution {\n    public int containVirus(int[][] grid) {\n        int[] cost = new int[]{0};\n        while(check(grid, cost));\n        return cost[0];\n    }\n    \n    private boolean check(int[][] grid, int[] cost) {\n// update every day information and return false if no improvement can be made\n        int count = 1;\n        int max = -1;\n        boolean flag = false;\n        List<int[]> info = new ArrayList<>();\n        for (int i = 0; i < grid.length; i++) {\n            for (int j = 0; j < grid[0].length; j++) {\n                if (grid[i][j] == 1) {\n                    count++;\n                    int[][] walls = new int[grid.length][grid[0].length];\n                    int[] res = new int[2];\n                    grid[i][j] = count;\n                    dfs(i, j, grid, count, walls, res);\n                    if (res[0] != 0) flag = true;\n                    if (max == -1 || res[0] > info.get(max)[0]) {\n                        max = count - 2;\n                    }\n                    info.add(res);\n                }\n            }\n        }\n        if (count == 1) {\n            return false;\n        }\n        cost[0] += info.get(max)[1];\n        update(grid, max + 2);\n        return flag;\n    }\n    \n    \n    private void dfs(int row, int col, int[][] grid, int count, int[][] walls, int[] res) {\n//dfs and record number of walls need to block this area and how many 0s are under infection\n        int[] shiftX = new int[]{1, 0, -1, 0};\n        int[] shiftY = new int[]{0, 1, 0, -1};\n        \n        for(int i = 0; i < 4; i++) {\n            int newRow = row + shiftX[i];\n            int newCol = col + shiftY[i];\n            if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid[0].length) {\n                if (grid[newRow][newCol] == 1) {\n                    grid[newRow][newCol] = count;\n                    dfs(newRow, newCol, grid, count, walls, res);\n                } else if (grid[newRow][newCol] == 0) {\n                    if (walls[newRow][newCol] == 0) res[0]++;\n                    if ((walls[newRow][newCol] & 1 << i) == 0) {\n                        res[1]++;\n                        walls[newRow][newCol] |= 1 << i;\n                    }\n                }\n            }\n        }\n    }\n        \n        \n    private void update(int[][] grid, int quarantine) {\n//set the new infected area and set blocked area to be -1\n        int[] shiftX = new int[]{1, 0, -1, 0};\n        int[] shiftY = new int[]{0, 1, 0, -1};\n            \n        for (int i = 0; i < grid.length; i++) {\n            for (int j = 0; j < grid[0].length; j++) {\n                if (grid[i][j] > 1 && grid[i][j] != quarantine) {\n                    for (int k = 0; k < 4; k++) {\n                        int newRow = i + shiftX[k];\n                        int newCol = j + shiftY[k];\n                        if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid[0].length && grid[newRow][newCol] == 0) {\n                            grid[newRow][newCol] = 1;\n                        }\n                    }\n                    grid[i][j] = 1;\n                } else if (grid[i][j] == quarantine) {\n                    grid[i][j] = -1;\n                }\n            }\n        }\n    }     \n}\n```
[]