Python - DFS + Dictionary Method
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        \n        M,N = len(isInfected),len(isInfected[0])\n        if M == N == 1:\n            return 0\n\n        directions = [(1,0),(-1,0),(0,1),(0,-1)]\n\n        def inbound(pt):\n            return M > pt[0] >= 0 <= pt[1] < N\n\n        virusLoc = set()\n        for i in range(M):\n            for j in range(N):\n                if isInfected[i][j]:\n                    virusLoc.add((i,j))\n\n        #DFS walk through virus regions\n        def walker(pt, regionId):\n            (r,c) = pt\n            virusRegion[regionId].add((r,c))\n            virusLoc.remove((r,c))\n            neighbors = [(r+d[0],c+d[1]) for d in directions]\n            neighbors = [n for n in neighbors if inbound(n)]\n            for (x,y) in neighbors:\n                if (x,y) in virusLoc:\n                    walker((x,y), regionId)\n            return\n\n        #populate virusRegion dictionary\n        virusRegion = defaultdict(set)\n        id = 1\n        while virusLoc:\n            virusLoc.add(seed := virusLoc.pop())\n            walker(seed,id)\n            id += 1\n \n        #wall off specific virus cluster by flipping sign of id\n        def wallOff(id):\n            virusRegion[-id] = virusRegion.pop(id)\n\n        #helper function to display remaining active regions\n        def printVirusRegion():\n            for id in virusRegion.keys():\n                if id > 0:\n                    print("ID:", id, virusRegion[id])\n\n        #printVirusRegion()\n\n        #populate each virus region\n        def spreadVirus(id):\n            allVirus = set(chain.from_iterable(virusRegion.values()))\n            VR = set()\n\n            for (r,c) in virusRegion[id].copy():\n                VR.add((r,c))\n                neighbors = [(r+d[0],c+d[1]) for d in directions]\n                neighbors = [n for n in neighbors if inbound(n)]\n                for n in neighbors:\n                    if not n in allVirus:\n                        VR.add(n)\n            return VR\n\n\n        def findRegionToWallOff():\n            regionToWallOff = 0\n            maxSpread = -1\n            for id in [id for id in virusRegion.keys() if id > 0]:\n                deltaSpread = len(spreadVirus(id)) - len(virusRegion[id])\n                if  deltaSpread > maxSpread:\n                    maxSpread = deltaSpread\n                    regionToWallOff = id\n\n            return regionToWallOff\n          \n        #combine regions - critical (can be further optimized)\n        def combineRegions():\n            regions = [id for id in list(virusRegion.keys()) if id>0]\n\n            regionsMerged = 0\n            for id0 in regions:\n                v0 = virusRegion[id0]\n                n0 = [[(r+d[0],c+d[1]) for d in directions] for (r,c) in v0]\n                n0 = set(chain.from_iterable(n0))\n                for id1 in regions:\n                    if id0 != id1:\n                        v1 = virusRegion[id1]\n                        if n0.intersection(v1):\n                            print("Merging regions:", id0, id1)\n                            regionsMerged += 1\n                            virusRegion[id0] = virusRegion[id0].union(virusRegion.pop(id1))\n\n            for id in list(virusRegion.keys()):\n                if not virusRegion[id]:\n                    print("Deleting region:", id)\n                    del virusRegion[id]\n\n            return regionsMerged\n\n        #count number of walls (negative regions only!)\n        def countWalls(id):\n            allVirus = set(chain.from_iterable(virusRegion.values()))\n            ct = 0\n            for (r,c) in virusRegion[id]:\n                neighbors = [(r+d[0],c+d[1]) for d in directions]\n                neighbors = [n for n in neighbors if inbound(n)]\n                for n in neighbors:\n                    if not n in allVirus:\n                        ct+=1\n            return ct\n\n        totalWalls = 0\n        while max(virusRegion.keys()) > 0:\n\n            #count number of walls used for this wall-off\n            wallOffId = findRegionToWallOff()\n            wallOff(wallOffId)\n            wallsUsed = countWalls(-wallOffId)\n            totalWalls += wallsUsed\n            \n            #spread "simultaneously", not iterative.\n            nextSpread = defaultdict(set)\n            for id in [id for id in virusRegion.keys() if id > 0]:\n                nextSpread[id] = spreadVirus(id)           \n            for id in [id for id in virusRegion.keys() if id > 0]: \n                virusRegion[id] = nextSpread[id]\n\n            while combineRegions():\n                0   #do nothing, just needs to combine\n            \n        print("Quarantine Complete")\n\n        return totalWalls\n```
['Python3']