Python Object Oriented Solution - Easy to understand
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is Python version:\nFor explanation please refer CPP Version\nCredit goes to: rai0
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is Python version:\nFor explanation please refer [CPP Version](https://leetcode.com/problems/contain-virus/solutions/847507/cpp-dfs-solution-explained/)\nCredit goes to: [rai02](https://leetcode.com/rai02/)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nDFS with Creating Cluster objects(for walls,tobeContaminated cells)\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(M*N)^^2\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(M*N)\n# Code\n```\nfrom heapq import heapify,heappush,heappop\nclass Cluster:\n    def __init__(self):\n        self.contaminated = set()\n        self.toBeContaminated = set()\n        self.wallCnt = 0\n    # sorting based on # of toBeContaminated in reverse order\n    def __lt__(self,nxt):\n        return len(self.toBeContaminated) > len(nxt.toBeContaminated)\n\nclass Solution:\n\n    def containVirus(self, isInfected: List[List[int]]) -> int:\n        rows = len(isInfected)\n        cols = len(isInfected[0])\n        ans = 0\n        \n        def dfs(i,j,cluster):\n            dirs = [(1,0),(-1,0),(0,1),(0,-1)]\n            for r,c in dirs:\n                nr = i + r\n                nc = j + c\n                if 0<=nr<rows and 0<=nc<cols:\n                    if isInfected[nr][nc]==1 and (nr,nc) not in visited:\n                        cluster.contaminated.add((nr,nc))\n                        visited.add((nr,nc))\n                        dfs(nr,nc,cluster)\n                    elif isInfected[nr][nc]==0:\n                 # note: we dont add to visited here as two virus cells can attack common normal cell\n                        cluster.wallCnt += 1\n                        cluster.toBeContaminated.add((nr,nc))\n\n\n        while True:\n            visited = set()\n            hh = []\n            for i in range(rows):\n                for j in range(cols):\n                    if isInfected[i][j]==1 and (i,j) not in visited:\n                        cluster = Cluster()\n                        cluster.contaminated.add((i,j))\n                        visited.add((i,j))\n                        dfs(i,j,cluster)\n                        hh.append(cluster)\n            if not hh:\n                break\n            heapify(hh)\n            # this will return cluster with max toBeContaminated cells\n            cluster = heappop(hh)\n            # stopping the virus by building walls\n            for i,j in cluster.contaminated:\n                isInfected[i][j] = -1\n            ans += cluster.wallCnt\n\n            while hh:\n                cluster = hh.pop()\n                for i,j in cluster.toBeContaminated:\n                    isInfected[i][j] = 1\n\n        return ans\n\n\n\n\n\n\n\n\n```
['Depth-First Search', 'Python3']