My ugly java DFS solution 19 ms with explaination
The test case 3 is wrong. It should be 13 instead of 11.\nThe idea is to use dfs for each group of virus to find out how many cells will be infected and how man
The test case 3 is wrong. It should be 13 instead of 11.\nThe idea is to use dfs for each group of virus to find out how many cells will be infected and how many walls will be needed. If an adjacent good cells has been visited, next time it is reached by dfs, the count for walls still need to increase 1.\nThen we selected the group of virus with maximum number of new cells to be infected, and label/fix them. We keep this process until no new cells will be infected, which means either the spread is stopped or all the cells are infected.\n```\nclass Solution {\n    int[][] dir = {{0,1},{0,-1},{-1,0},{1,0}};\n    int m, n;\n    public int containVirus(int[][] grid) {\n    \tm = grid.length; n = grid[0].length;\n    \tint res = 0;\n    \twhile (true) {\n\t    \tboolean [][] v = new boolean[m][n];\n\t    \tint[] cur = new int[4];\t\t// cur[0] represents how many cell will be infected by this group tomorrow, cur[1] represents how many walls will be built if this group is chosen. cur[2] and cur[3] represents the start of the selected group   \n\t    \tfor (int i=0;i<m;i++) {\n\t    \t\tfor (int j=0;j<n;j++) {\n\t    \t\t\tif (grid[i][j]==1 && !v[i][j]) {\n\t    \t\t\t\tboolean[][] z = new boolean[m][n];\t// z[i][j] represents if the cell is checked. if it's checked, cur[0] won't be counted, but cur[1] still need to increase 1;\n\t    \t\t\t\tint[] rt = new int[2];\n\t    \t\t\t\tdfs(grid,v,z,rt,i,j);\n\t    \t\t\t\tif (rt[0]>cur[0]) {\n\t    \t\t\t\t\tcur[0] = rt[0];\n\t    \t\t\t\t\tcur[1] = rt[1];\n\t    \t\t\t\t\tcur[2] = i;\n\t    \t\t\t\t\tcur[3] = j;\n\t    \t\t\t\t}\n\t    \t\t\t}\n\t    \t\t}\n\t    \t}\n\t    \tif (cur[0] == 0) {\n\t    \t\treturn res;\n\t    \t}\n\t    \tres += cur[1];\n\t    \tdfs1(grid, cur[2], cur[3]);\n\t    \tfor (int i=0;i<m;i++) {\n\t    \t\tfor (int j=0;j<n;j++) {\n\t    \t\t\tif (grid[i][j]==0) {\n\t    \t\t\t\tfor(int k=0;k<4;k++) {\n\t    \t\t    \t\tint x = i+dir[k][0], y = j+dir[k][1];\n\t    \t\t    \t\tif (x>=0 && x<m && y>=0 && y<n) {\n\t    \t\t    \t\t\tif (grid[x][y]==1) {\n\t    \t\t    \t\t\t\tgrid[i][j] = 3;\n\t    \t\t    \t\t\t\tbreak;\n\t    \t\t    \t\t\t}\n\t    \t\t    \t\t}\n\t    \t\t\t\t}\n\t    \t\t\t}\n\t    \t\t}\n    \t\t}\n\t    \tfor (int i=0;i<m;i++) {\n\t    \t\tfor (int j=0;j<n;j++) {\n\t    \t\t\tif (grid[i][j]==3) {\n\t    \t\t\t\tgrid[i][j]=1;\n\t    \t\t\t}\n\t    \t\t}\n    \t\t}\n    \t}\n    }\n    void dfs1(int[][]grid, int i, int j) {\t\t// change the selected cells from 1 to 2. these cells will be fixed and we won't touch them anymore. \n    \tgrid[i][j] = 2;\n    \tfor(int k=0;k<4;k++) {\n    \t\tint x = i+dir[k][0], y = j+dir[k][1];\n    \t\tif (x>=0 && x<m && y>=0 && y<n) {\n    \t\t\tif (grid[x][y]==1) {\n    \t\t\t\tdfs1(grid,x,y);\n    \t\t\t}\n    \t\t}\n    \t}\n    }\n    void dfs(int[][]grid, boolean[][]v, boolean[][] z, int[] rt,int i, int j) {\n    \tint[] res = new int[2];\n    \tv[i][j] = true;\n    \tfor(int k=0;k<4;k++) {\n    \t\tint x = i+dir[k][0], y = j+dir[k][1];\n    \t\tif (x>=0 && x<m && y>=0 && y<n) {\n    \t\t\tif (grid[x][y]==0) {\n    \t\t\t\trt[1]++;\n    \t\t\t\tif (!z[x][y]) {\n    \t\t\t\t\tz[x][y] = true;\n    \t\t\t\t\trt[0]++;\n    \t\t\t\t}\n    \t\t\t}\n    \t\t\tif (grid[x][y]==1 && !v[x][y]) {\n    \t\t\t\tdfs(grid,v,z,rt,x,y);\n    \t\t\t}\n    \t\t}\n    \t}\n    }\n}\n```
[]