Python BFS simulation solution: nothing convoluted
I guess one should attempt Leetcode 695. Max Area of Island before doing this problem. Just speeds up everything tremendously, no complicated algorithms or conc
I guess one should attempt Leetcode 695. Max Area of Island before doing this problem. Just speeds up everything tremendously, no complicated algorithms or concepts at all\nAlso, I highly recommend padding the boundary with 2, as a rigid wall is equivalent to a quarantined region\n```\nclass Solution:\n    # Use 2 to pad the boundary\n    # Cycle start\n    # Use BFS to identify connected components\n    # In the process also calculate the perimeter\n    # Important point to note: we choose group with largest number of 0 cells neighboring the 1s, not the perimeter\n    # Choose region with the affected neighbours to install wall (perimeter), mark the region to be 2\n    # Then for all infected regions, expand the boundary for 1\n    # Repeat the cycle until all regions become 2 (len(points) <= 1)\n    \n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        # Boundary padding\n        self.grid = [[2]*(len(isInfected[0])+2)]\n        for row in isInfected:\n            self.grid.append([2] + row + [2])\n        self.grid.append([2]*(len(isInfected[0])+2))\n        \n        # reused Leetcode 695. Max Area of Island code\n        # BFS from each point with 1 \n        m, n = len(self.grid), len(self.grid[0])\n        neig = [[1,0],[-1,0],[0,1],[0,-1]]\n        wall = 0\n        finished = False\n        \n        while not finished:\n            island_perimeters = []\n            affected_cells = []\n            points = []\n            visited = set()\n            for i in range(1,m-1):\n                for j in range(1,n-1):\n                    if self.grid[i][j] == 1 and (i,j) not in visited:\n                        # BFS\n                        points.append(set())\n                        affected_cells.append(set())\n                        dq = deque()\n                        dq.append((i,j))\n                        visited.add((i,j))\n                        perimeter = 0\n                        while dq:\n                            x = dq.popleft()\n                            for k in range(4):\n                                xn, yn = x[0]+neig[k][0], x[1]+neig[k][1]\n                                if (xn,yn) not in visited and self.grid[xn][yn]==1:\n                                    dq.append((xn,yn))\n                                    visited.add((xn,yn))\n                                elif self.grid[xn][yn] == 0:\n                                    perimeter += 1\n                                    affected_cells[-1].add((xn,yn))\n                            points[-1].add(x)\n                        island_perimeters.append(perimeter)\n            if not points:\n                return wall\n            max_affected, max_group = 0, 0\n            for i, cells in enumerate(affected_cells):\n                if len(cells) > max_affected:\n                    max_group =  i\n                    max_affected = len(cells)\n            wall += island_perimeters[max_group]\n                                       \n            # quarantined regions\n            for point in points[max_group]:\n                self.grid[point[0]][point[1]] = 2\n            # evolve the infection\n            if len(points) == 1:\n                finished = True\n            else:\n                for j, point_set in enumerate(points):\n                    if j != max_group:\n                        for point in point_set:\n                            for k in range(4):\n                                xn, yn = point[0]+neig[k][0], point[1]+neig[k][1]\n                                if self.grid[xn][yn] == 0:\n                                    self.grid[xn][yn] = 1\n        return wall\n```
[]