题目描述

题意：病毒扩散得很快，现在你的任务是尽可能地通过安装防火墙来隔离病毒。假设世界由二维矩阵组成，0 表示该区域未感染病毒，而 1 表示该区域已感染病毒。可以在任意 2 个四方向相邻单元之间的共享边界上安装一个防火墙（并且只有一个防火墙）。每天晚上，病毒会从被感染区域向相邻未感染区域扩散，除非被防火墙隔离。现由于资源有限，每天你只能安装一系列防火墙来隔离其中一个被病毒感染的区域（一个区域或连续的一片区域），且该感染区域对未感染区域的威胁最大且保证唯一。

你需要努力使得最后有部分区域不被病毒感染，如果可以成功，那么返回需要使用的防火墙个数; 如果无法实现，则返回在世界被病毒全部感染时已安装的防火墙个数。

样例

Input: grid = 
[[0,1,0,0,0,0,0,1],
 [0,1,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,1],
 [0,0,0,0,0,0,0,0]]
Output: 10
Explanation:
There are 2 contaminated regions.
On the first day, add 5 walls to quarantine the viral region on the left. The board after the virus spreads is:

[[0,1,0,0,0,0,1,1],
 [0,1,0,0,0,0,1,1],
 [0,0,0,0,0,0,1,1],
 [0,0,0,0,0,0,0,1]]

On the second day, add 5 walls to quarantine the viral region on the right. The virus is fully contained.

算法1

(模拟)

题解：题目已经跟明显的提示出每天对未感染区域威胁最大的感染区域是唯一的了，那么我们现在要做的就是：

• 遍历所有的感染区域，对于每个感染区域求出他的威胁的区域以及其面积（与当前连通分量相邻的0），如果需要隔离这个区域需要多少个防火墙。
• 在所有连通区域中选择威胁面积最大的那个连通分量进行隔离，将剩余的连通分量威胁的区域进行感染。
• 重复上述操作，直至病毒无法扩散或者已经扩散完了。

时间复杂度分析：理论上最多$(n+m)$天可以扩展完整个区域，每天需要对整个区域进行遍历$O(n*m)$。

所以总的时间复杂度为$ O(n*m)(n+m) $

C++ 代码

vis:标记每一天哪些区域已经被遍历过了
virus_area：存储了今天需要被隔离的坐标
nexts：存储了每个病毒区域威胁的区域坐标
block_index:当前威胁最大的区域下标
blovk_walls：当前威胁最大的区域需要建设多少个防火墙

cnt:统计当前连通区域威胁的区域大小
cur：当前连通区域的坐标
next:当前连通区域明天会扩散到哪些区域的坐标

class Solution {
public:
    int n,m,res = 0,dx[4] = {0,-1,0,1},dy[4] = {-1,0,1,0};
    int containVirus(vector<vector<int>>& grid)
    {
        n = grid.size(),m = grid[0].size();
        while(true)
        {
            vector<int> vis(n * m,0);
            vector<int> virus_area;
            vector<unordered_set<int>> nexts;
            int block_index = -1,block_walls = -1;
            for(int i = 0 ; i < n ; i ++)
            {
                for(int j = 0 ; j < m ; j ++)
                {
                    int key = i * m + j,cnt = 0;
                    if(grid[i][j] != 1 || vis[key]) continue;
                    vector<int> cur;
                    unordered_set<int> next;
                    bfs(grid,i,j,vis,cur,next,cnt);
                    if(next.empty()) continue;
                    if(nexts.empty() || next.size() > nexts[block_index].size())
                    {
                        virus_area.swap(cur);
                        block_index = nexts.size();
                        block_walls = cnt;
                    }
                    nexts.push_back(next);
                }
            }
            if(nexts.empty()) break;
            res += block_walls;
            for(int i = 0 ; i < nexts.size() ; i ++)
            {
                if(i == block_index)
                {
                    for(auto key:virus_area)
                    {
                        int x = key / m,y = key % m;
                        grid[x][y] = 2;
                    }
                }else
                {
                    for(auto key:nexts[i])
                    {
                        int x = key / m,y = key % m;
                        grid[x][y] = 1;
                    }
                }
            }
        }
        return res;
    }
    void bfs(vector<vector<int>> &grid,int r,int c,vector<int> &vis,vector<int>& cur,unordered_set<int>& next,int& cnt)
    {

        if(r < 0 || r >= n || c < 0 || c >= m || grid[r][c] == 2) return;
        int key = r * m + c;
        if(grid[r][c] == 0)
        {
            cnt ++;
            next.insert(key);
            return;
        }
        if(vis[key]) return;
        vis[key] = 1;
        cur.push_back(key);
        for(int i = 0 ; i < 4 ;i ++)
        {
            int x = r + dx[i],y = c + dy[i];
            bfs(grid,x,y,vis,cur,next,cnt);
        }
    }
};