cell contained python bfs
0: is a free cell\n1: is a contaminated cell that is spreading\n-1: is a contaminated cell that we stopped spreading\n\nfor each connected component of 1s\n1. a
0: is a free cell\n1: is a contaminated cell that is spreading\n-1: is a contaminated cell that we stopped spreading\n\nfor each connected component of 1s\n1. a hashset of all the connected cells under this same connected component\n2. the number of walls it would take to quarantine this cc\n3. the number of cells it would contaminate if we let it spread one turn\n\npseudo code\n```\nareas = getallccs()\nwhile(areas):\n\tget the max area aka the one that stop the spread of the max number of cells\n\tarea = the max among all areas\n\ttotal += the number of walls for that area\n\tturn this area into -1 aka stop the propagation\n\tareas = getallccs() # recompute the areas\n```\n\nhow many walls given a cc?\n\ngiven a cell , look at its 4 neighbors, \nit one of them is a zero , it needs one wall\ndo that for all the cells\n\n\nhow many walls possible contaminations?\n\ngiven a cell , look at its 4 neighbors, \nit one of them is a zero , add it to a hashset\ndo that for all the cells\nand the length of that hashset if \nthe number of possible contamination\nhashset because a zero could be surrounded and counted multiple times\n\n\n\n\n\n```\nclass Solution(object):\n    def containVirus(self, grid):\n        total,areas = 0,self.f(grid)\n        while(areas):\n            areas.sort(key = lambda x: (x[2], -x[1]))\n            total += areas[-1][1]\n            self.quarantine(areas[-1][0],grid)\n            areas.pop()\n            self.spread(grid)\n            areas = self.f(grid)\n        return total\n    \n    def f(self,grid):\n        areas = []\n        gv = set([])\n        for i in range(len(grid)):\n            for j in range(len(grid[0])):\n                if grid[i][j] == 1 and (i,j) not in gv: \n                    nw = 0\n                    q = collections.deque([(i,j)])\n                    vis = set([(i,j)])\n                    nb = set([])\n                    while(q):\n                        u = q.popleft()\n                        for v in [(u[0]+1,u[1]), (u[0]-1,u[1]), (u[0],u[1]+1), (u[0],u[1]-1)]:\n                            if 0<= v[0] < len(grid) and 0 <= v[1] < len(grid[0]) and v not in vis:\n                                if grid[v[0]][v[1]] == 1:\n                                    q.append(v)\n                                    gv.add(v)\n                                    vis.add(v)\n                                elif grid[v[0]][v[1]] == 0:\n                                    nb.add(v)\n                                    nw +=1\n                    areas.append([vis,nw,len(nb)])\n        return areas\n    def quarantine(self,area,grid): for ei,ej in area: grid[ei][ej] = -1\n    def spread(self,grid):\n        ta = [(i,j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j] ==1]\n        for u in ta:\n            for v in [(u[0]+1,u[1]), (u[0]-1,u[1]), (u[0],u[1]+1), (u[0],u[1]-1)]:\n                if 0<= v[0] < len(grid) and 0 <= v[1] < len(grid[0]) and grid[v[0]][v[1]] == 0: grid[v[0]][v[1]] = 1\n```
[]