[749. Isolate virus]

source ： Power button （LeetCode）

describe ：

The virus spreads quickly , Now your task is to install the firewall to isolate the virus as much as possible .

Suppose the world is made up of m x n Two dimensional matrix of isInfected form , isInfected[i][j] == 0 It means that the area is not infected with virus , and isInfected[i][j] == 1 Indicates that the area is infected with virus . It can be done anywhere 2 Install a firewall on the shared boundary between adjacent units （ And there's only one firewall ）.

Every night , The virus will spread from the infected area to the adjacent uninfected area , Unless it's isolated by a firewall . Now due to limited resources , Every day you can only install a series of firewalls to isolate one of the infected areas （ An area or continuous area ）, And the infected area is the greatest threat to the uninfected area and Ensure that the only .

You need to try to keep some areas from getting infected , If it can succeed , Then return the number of firewalls to be used ; If it doesn't work , Then it returns the number of firewalls installed when the world is infected by all viruses .

Example 1：

 Input : isInfected = [[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
 explain : There are two infected areas .
 On the first day , add to  5  The wall isolates the left side of the virus area . The state of the virus after transmission is :
 the second day , Add... To the right  5  A wall to isolate the virus area . At this time, the virus has been completely controlled .

Example 2：

 Input : isInfected = [[1,1,1],[1,0,1],[1,1,1]]
 Output : 4
 explain :  Although only a small area is saved , But there are four walls .
 Be careful , The firewall is only built on the shared boundary of two different areas .

Example 3:

 Input : isInfected = [[1,1,1,0,0,0,0,0,0],[1,0,1,0,1,1,1,1,1],[1,1,1,0,0,0,0,0,0]]
 Output : 13
 explain :  After isolating the infected area on the right , To isolate the virus area on the left, we only need  2  A firewall .

Tips :

• m == isInfected.length
• n == isInfected[i].length
• 1 <= m, n <= 50
• isInfected[i][j] is either 0 or 1
• Throughout the description , There is always an adjacent virus region , It will be in the next round Strictly infect more uncontaminated cubes

Method ： Breadth first search

Ideas and algorithms

This question only needs to be simulated according to the meaning of the question , But there are many details , You need to write code carefully .

First, we can compare the matrix isInfected Do breadth first search , In particular , When we traverse to isInfected One of them 1 when , From this 1 Start breadth first search at the corresponding position , In this way, you can get a continuous area infected by the virus .

In the process of searching , If it's No idx (idx≥1) An area infected by a virus , That's all we have to do 1 All assigned to −idx, This will prevent repeated searches , And it can interact with non viral areas 0 Distinguish . meanwhile , Because every time we need to choose 「 The greatest threat to uninfected areas 」 Firewall for the zone , So we also need to store ：

• The uninfected area adjacent to this area （ namely 0） Location and number of ;

• If you need to set a firewall in this area , Then you need the number of firewalls .

For the former , We are in the process of breadth first search , Just expand 1 Search for adjacent 0, You can put this 0 The corresponding position is placed in a hash set . The reason for using hash sets here is the same 0 May be associated with multiple 1 adjacent , Can prevent double counting . meanwhile , Due to the multiple 1 It may appear in different infected areas , If by modifying the matrix isInfected To mark these 0, It will make coding more troublesome .

For the latter , The calculation method is similar , Expanding 1 If you search for adjacent 0, Then we need to be in 1 and 0 A firewall is built on the edge of the grid between . The same 0 And multiple 1 adjacent , You need to build multiple firewalls , Therefore, we only need to use one variable to count in the process of breadth first search , There is no need to consider repetition .

After breadth first search , If we don't find any infected areas , It indicates that there is no virus in the area , We go straight back 0 As the answer . otherwise , We need to find 「 The greatest threat to uninfected areas 」 Region , Here, you only need to find the region with the largest size of the corresponding hash set .

After determining the area （ Suppose it's the idx area ） after , Let's put all the in the matrix −idx All become 2, This will not affect any search and judgment ; All other negative numbers are restored to 1. Besides , Stored in all hash sets （ Except for idx Other than the corresponding block area ） All adjacent locations need to be from 0 become 1, Indicates the spread of the virus .

Last , If we find that there is only one area , After the firewall is established , There will be no more virus transmission , You can return the answer ; Otherwise, we need to continue to repeat all the above steps .

Code ：

class Solution {
    
private:
    static constexpr int dirs[4][2] = {
    {
    -1, 0}, {
    1, 0}, {
    0, -1}, {
    0, 1}};
public:
    int containVirus(vector<vector<int>>& isInfected) {
    
        auto pair_hash = [fn = hash<int>()](const pair<int, int>& o) {
    
            return (fn(o.first) << 16) ^ fn(o.second);
        };

        int m = isInfected.size(), n = isInfected[0].size();
        int ans = 0;
        while (true) {
    
            vector<unordered_set<pair<int, int>, decltype(pair_hash)>> neighbors;
            vector<int> firewalls;
            for (int i = 0; i < m; ++i) {
    
                for (int j = 0; j < n; ++j) {
    
                    if (isInfected[i][j] == 1) {
    
                        queue<pair<int, int>> q;
                        unordered_set<pair<int, int>, decltype(pair_hash)> neighbor(0, pair_hash);
                        int firewall = 0, idx = neighbors.size() + 1;
                        q.emplace(i, j);
                        isInfected[i][j] = -idx;

                        while (!q.empty()) {
    
                            auto [x, y] = q.front();
                            q.pop();
                            for (int d = 0; d < 4; ++d) {
    
                                int nx = x + dirs[d][0];
                                int ny = y + dirs[d][1];
                                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
    
                                    if (isInfected[nx][ny] == 1) {
    
                                        q.emplace(nx, ny);
                                        isInfected[nx][ny] = -idx;
                                    }
                                    else if (isInfected[nx][ny] == 0) {
    
                                        ++firewall;
                                        neighbor.emplace(nx, ny);
                                    }
                                }
                            }
                        }
                        neighbors.push_back(move(neighbor));
                        firewalls.push_back(firewall);
                    }
                }
            }
            
            if (neighbors.empty()) {
    
                break;
            }

            int idx = max_element(neighbors.begin(), neighbors.end(), [](const auto& v0, const auto& v1) {
     return v0.size() < v1.size(); }) - neighbors.begin();
            ans += firewalls[idx];
            for (int i = 0; i < m; ++i) {
    
                for (int j = 0; j < n; ++j) {
    
                    if (isInfected[i][j] < 0) {
    
                        if (isInfected[i][j] != -idx - 1) {
    
                            isInfected[i][j] = 1;
                        }
                        else {
    
                            isInfected[i][j] = 2;
                        }
                    }
                }
            }
            for (int i = 0; i < neighbors.size(); ++i) {
    
                if (i != idx) {
    
                    for (const auto& [x, y]: neighbors[i]) {
    
                        isInfected[x][y] = 1;
                    }
                }
            }
            if (neighbors.size() == 1) {
    
                break;
            }
        }
        return ans;
    }
};

Execution time ：20 ms, In all C++ Defeated in submission 69.23% Users of
Memory consumption ：12 MB, In all C++ Defeated in submission 78.32% Users of
Complexity analysis
Time complexity ： O( mn (m + n)). The time required for each breadth first search is O(mn), The maximum Manhattan distance of any two positions in the matrix is m + n − 2, So in O(m + n) After the search , All the viruses that have not been isolated will be connected as a whole .
Spatial complexity ： O(mn), That is, the space needed by the queue and hash set in breadth first search .
author：LeetCode-Solution