Approach #1: Simulation [Accepted]

Intuition

Let's work on simulating one turn of the process. We can repeat this as necessary while there are still infected regions.

Algorithm

Though the implementation is long, the algorithm is straightforward. We perform the following steps:

  • Find all viral regions (connected components), additionally for each region keeping track of the frontier (neighboring uncontaminated cells), and the perimeter of the region.

  • Disinfect the most viral region, adding it's perimeter to the answer.

  • Spread the virus in the remaining regions outward by 1 square.

Complexity Analysis

  • Time Complexity: where is the number of rows and columns. After time , viral regions that are alive must have size at least , so the total number removed across all time is .

  • Space Complexity: in additional space.


Analysis written by: @awice.