Problem statement

https://leetcode.com/problems/contain-virus/

Solution

The idea is to traverse our grid several times, each time working with the

  1. islands: our regions of contamination, connected region with all 1 inside
  2. perimeters is perimeter of each region, we can calculate it during our dfs stage: if current value of cell is 1 and value for neighbor is 0, we add 1 to perimeter
  3. frontiers: similar to perimeters, but here we add coordinates of cell. Also it is set here, to avoid duplicates.

Now, we continue to do the following code until we can:

  1. Create empty perimeters, islands, frontiers, seen, count.
  2. Run dfs from every not visited cell of our grid, such that it has virus, that is value is equal to 1. When we run this dfs, perimeters, islands, frontiers will be updated.
  3. Stopping criteria is count == 0 or empty frontiers.
  4. Now, we find the region we need to build wall around and add perimeter of this region to final answer.
  5. We iterate over our islands and for all of them which are without wall, we update all frontier equal to 1. Finally, we mark our quarantined island with new value: 2. Why we need this? Then in new iteration, frontier and perimeter will be evaluated correctly: our dfs will not visit nodes equal to 2, it will just ignore them. Also each wall will be counter only once.

Complexity

Space complexity is O(mn). Time complexity can be estimated as O(m^2n^2), which is quite weak estimation. We are stated, that we will never have a tie, and leetcode says it is O((mm)^{4/3}) without strict proof, which seems fine, but need to be proved.

Code

```pythonclass Solution: def containVirus(self, grid): m, n, ans = len(grid), len(grid[0]), 0 neib_list = [[1,0],[-1,0],[0,-1],[0,1]]

    def dfs(t, x, y):
        if (x, y) in seen: return
        islands[t].append((x, y))
        seen.add((x, y))
        for dx, dy in neib_list:
            if 0<=x+dx<m and 0<=y+dy<n:
                if grid[x+dx][y+dy] == 1:
                    dfs(t, x+dx, y+dy)
                elif grid[x+dx][y+dy] == 0:
                    frontiers[t].add((x+dx,y+dy))
                    perimeters[t] += 1
            
    while True:    
        islands = defaultdict(list)
        perimeters = defaultdict(int)
        frontiers = defaultdict(set)
        seen, count = set(), 0
        
        for i,j in product(range(m), range(n)):
            if (i,j) not in seen and grid[i][j] == 1:
                dfs(count, i, j)
                count += 1

        if count == 0 or not frontiers: break
        
        quarantine = max(frontiers.items(), key = lambda x: len(x[1]))[0]
        ans += perimeters[quarantine]
        for i in range(count):
            if i != quarantine:
                for x, y in frontiers[i]: grid[x][y] = 1

        for x,y in islands[quarantine]: grid[x][y] = 2

    return ans ```