Contain Virus Solution in C++

Problem Description

Ah, the classic “Contain Virus” problem! Imagine you’re a city planner, and your town is facing a viral outbreak. You know, the kind that spreads faster than gossip at a family reunion. Your goal? To build walls around the infected regions to prevent the virus from spreading further. But wait! You also need to ensure that you build the walls in such a way that you minimize the number of walls needed. It’s like playing a game of Tetris, but instead of fitting blocks, you’re trying to contain a viral menace.

In this problem, you’re given a grid where 1 represents an infected cell, 0 represents a non-infected cell, and 2 represents a cell that has been contained. Your task is to determine the minimum number of walls required to contain the virus effectively.

Code Solution


struct Region {
  unordered_set infected;
  unordered_set noninfected;
  int wallsRequired = 0;
};

class Solution {
 public:
  int containVirus(vector>& isInfected) {
    const int m = isInfected.size();
    const int n = isInfected[0].size();
    int ans = 0;

    while (true) {
      vector regions;
      vector> seen(m, vector(n));

      for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
          if (isInfected[i][j] == 1 && !seen[i][j]) {
            Region region;
            dfs(isInfected, i, j, region, seen);
            if (!region.noninfected.empty())
              regions.push_back(region);
          }

      if (regions.empty())
        break;

      ranges::sort(regions, ranges::less{}, [](const Region& region) {
        return region.noninfected.size();
      });

      Region mostInfectedRegion = regions.back();
      regions.pop_back();
      ans += mostInfectedRegion.wallsRequired;

      for (const int neighbor : mostInfectedRegion.infected) {
        const int i = neighbor / n;
        const int j = neighbor % n;
        isInfected[i][j] = 2;
      }

      for (const Region& region : regions)
        for (const int neighbor : region.noninfected) {
          const int i = neighbor / n;
          const int j = neighbor % n;
          isInfected[i][j] = 1;
        }
    }

    return ans;
  }

 private:
  void dfs(const vector>& isInfected, int i, int j, Region& region,
           vector>& seen) {
    if (i < 0 || i == isInfected.size() || j < 0 || j == isInfected[0].size())
      return;
    if (seen[i][j] || isInfected[i][j] == 2)
      return;
    if (isInfected[i][j] == 0) {
      region.noninfected.insert(i * isInfected[0].size() + j);
      ++region.wallsRequired;
      return;
    }

    seen[i][j] = true;
    region.infected.insert(i * isInfected[0].size() + j);

    dfs(isInfected, i + 1, j, region, seen);
    dfs(isInfected, i - 1, j, region, seen);
    dfs(isInfected, i, j + 1, region, seen);
    dfs(isInfected, i, j - 1, region, seen);
  }
};

Approach Explanation

The approach taken in this solution involves using Depth-First Search (DFS) to explore the grid and identify regions of infection. Each region is tracked using a Region struct that keeps track of infected cells, non-infected neighbors, and the number of walls required to contain it. The algorithm iteratively identifies the region that poses the greatest threat (i.e., the one that can infect the most non-infected cells) and builds walls around it while allowing other regions to spread their infection. This process continues until no more regions are left to process.

Time and Space Complexity

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. Each cell is visited at most once.

Space Complexity: O(m * n) for the seen matrix and the regions vector, which can store information about all cells in the worst case.

Real-World Example

Imagine a scenario where a new viral strain is spreading in a city. The health department needs to quickly identify the most dangerous areas and build quarantine zones (walls) to prevent further spread. By analyzing the grid of infected and non-infected areas, they can effectively contain the outbreak, ensuring that the virus doesn't spread to the entire city. This problem mirrors that real-world urgency and strategic planning.