DFS with "marker" , 15 ms
This problem is just a simulation.\nThe whole process is:\n1. Find which group of virus would infect most uninfected area. If no group of virus could infect mor
This problem is just a simulation.\nThe whole process is:\n1. Find which group of virus would infect most uninfected area. If no group of virus could infect more uninfected area, break.\n2. Deactive that group of virus.\n3. Let the rest group of virus spread.\nWe could use dfs to implement 1, 2, and 3. \nThe trickest part is to determine how many uninfected grid would a group of virus would infect in this round. \nIn case: \n1 0 \n1 1\n0 might be visited three times, however it should only appears once. If we simply use a "visited" array to memorize, the following case might happpen:\n1 0 1 0\n1 0 1 0\nDfs on the left group of virus would make the two 0 been "visited", but the right group needs to count these two 0 in its "infected number". If we do a memset for the whole "visited" array after each dfs call, it might cause TLE. \n\nSo we could use a marker to mark the "visited" array. Each dfs call would use a different marker, and the dfs would stop only when current marker == marker that marked the visited array.\n\n```\n#include <bits/stdc++.h>\nusing namespace std;\nint visited[51][51];\nint fx[] = {1, 0, -1, 0};\nint fy[] = {0, 1, 0, -1};\nclass Solution {\npublic:\n\tint m, n;\n\tbool valid(int i, int j) {\n\t\treturn i >= 0 && j >= 0 && i < m && j < n;\n\t}\n\n\tint dfs(int i, int j, vector<vector<int>>& isInfected, int marker) {\n\t\tif (!valid(i, j) || visited[i][j] || isInfected[i][j] != 1) return 0;\n\t\tvisited[i][j] = 1;\n\t\tint cnt = 0;\n\t\tfor (int k = 0; k < 4; k++) {\n\t\t\tint x = i + fx[k], y = j + fy[k];\n\t\t\tif (!valid(x, y)) continue;\n\t\t\tif (isInfected[x][y] == 0 && visited[x][y] != marker) {\n\t\t\t\tcnt++;\n\t\t\t\tvisited[x][y] = marker;\n\t\t\t} else if (isInfected[x][y] == 1) {\n\t\t\t\tcnt += dfs(x, y, isInfected, marker);\n\t\t\t}\n\t\t}\n\t\treturn cnt;\n\t}\n\n\tint buildWall(int i, int j, vector<vector<int>>& isInfected) {\n\t\tint cnt = 0;\n\t\tisInfected[i][j] = -1;\n\t\tfor (int k = 0; k < 4; k++) {\n\t\t\tint x = i + fx[k], y = j + fy[k];\n\t\t\tif (!valid(x, y)) continue;\n\t\t\tif (isInfected[x][y] == 1) {\n\t\t\t\tcnt += buildWall(x, y, isInfected);\n\t\t\t} else if (isInfected[x][y] == 0) {\n\t\t\t\tcnt++;\n\t\t\t}\n\t\t}\n\t\treturn cnt;\n\t}\n\n\tvoid spread(vector<vector<int>>& isInfected) {\n\t\tfor (int i = 0; i < m; i++) {\n\t\t\tfor (int j = 0; j < n; j++) {\n\t\t\t\tif (isInfected[i][j] != 0) continue;\n\t\t\t\tbool infect = 0;\n\t\t\t\tfor (int k = 0; k < 4; k++) {\n\t\t\t\t\tint x = i + fx[k], y = j + fy[k];\n\t\t\t\t\tif (valid(x, y) && isInfected[x][y] == 1) {\n\t\t\t\t\t\tinfect = true;\n\t\t\t\t\t\tbreak;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t\tif (infect) isInfected[i][j] = -2;\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 (isInfected[i][j] == -2) {\n\t\t\t\t\tisInfected[i][j] = 1;\n\t\t\t\t}\n\t\t\t}\n\t\t}\n\t}\n\tvoid print(vector<vector<int>>& isInfected) {\n\t\tfor (int i = 0; i < m; i++) {\n\t\t\tfor (int j = 0; j < n; j++) {\n\t\t\t\tcout << isInfected[i][j] << " ";\n\t\t\t}\n\t\t\tcout << endl;\n\t\t}\n\t\t\t\n\t}\n    int containVirus(vector<vector<int>>& isInfected) {\n\t\tint res = 0;\n\t\tm = isInfected.size();\n\t\tn = isInfected[0].size();\n        while (true) {\n\t\t\tmemset(visited, 0, sizeof(visited));\n\t\t\tint cx = -1, cy = -1, cv = 0;\n\t\t\tint hasGood = 0, marker = 4;\n\t\t\tfor (int i = 0; i < m; i++) {\n\t\t\t\tfor (int j = 0; j < n; j++) {\n                    hasGood = hasGood || isInfected[i][j] == 0;\n                    if (isInfected[i][j] != 1) continue;\n\t\t\t\t\tint tmp = dfs(i, j, isInfected, marker++);\n\t\t\t\t\tif (tmp > cv) {\n\t\t\t\t\t\tcv = tmp;\n\t\t\t\t\t\tcx = i;\n\t\t\t\t\t\tcy = j;\n\t\t\t\t\t}\n\t\t\t\t}\n\t\t\t}\n\t\t\tif (!cv || !hasGood) break;\n\t\t\tres += buildWall(cx, cy, isInfected);\n\t\t\tspread(isInfected);\n\t\t}\n\t\treturn res;\n\n    }\n};\n```
['Depth-First Search', 'Simulation']