leetcode749. Contain Virus

A virus is spreading rapidly, and your task is to quarantine the infected area by installing walls.

The world is modeled as a 2-D array of cells, where 0 represents uninfected cells, and 1 represents cells contaminated with the virus. A wall (and only one wall) can be installed between any two 4-directionally adjacent cells, on the shared boundary.

Every night, the virus spreads to all neighboring cells in all four directions unless blocked by a wall. Resources are limited. Each day, you can install walls around only one region – the affected area (continuous block of infected cells) that threatens the most uninfected cells the following night. There will never be a tie.

Can you save the day? If so, what is the number of walls required? If not, and the world becomes fully infected, return the number of walls used.

Example 1:
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.

Example 2:

Input: grid =

[[1,1,1],

[1,0,1],

[1,1,1]]

Output: 4

Explanation: Even though there is only one cell saved, there are 4 walls built.
Notice that walls are only built on the shared boundary of two different cells.

Example 3:

Input: grid =

[[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

Explanation: The region on the left only builds two new walls.
Note:

The number of rows and columns of grid will each be in the range [1, 50].

Each grid[i][j] will be either 0 or 1.
Throughout the described process, there is always a contiguous viral region that will infect strictly more uncontaminated squares in the next round.

int dirs[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
class Solution {
public:
    int m,n;
    int containVirus(vector<vector<int>>& grid) {
        m=grid.size();
        int total_walls=0;
        n=grid[0].size();        
        //对于每一天要重新搜索
        while(true){
            //
            vector<unorderedint>
            
           
            vector<int> vis;
             vector<int> nexts;
            
           vector<int> virus_area;//!!
            int best=0;
            int block_index=-1;
            int block_walls=-1;
            
            for(int x=0;x<m;x++){
                for(int y=0;y<n;y++){
                    {
                         int walls=0;
                         vector<int> curr;//!!
                        unordered_set<int> next;//!!
                         if(grid[x][y]==0||grid[x][y]==2) continue;
                         getArea(x,y,curr,vis,next,walls);
                         if(next.empty()) continue;
                         if(nexts.empty()||next.size()>best){
                             best=next.size();
                             virus_area.swap(curr)
                             block_index=nexts.size();
                             block_walls=walls;
                         }
                        nexts.push_back(std::move(next));//!!
                             
                    }       
                }
            }
            if(nexts.size()==0) break;
            totalwalls+=block_walls;
            for(int i=0;i<nexts.size();i++){
                
                if(i==block_index){
                    for(int key:virus_area){
                        grid[key/n][key%n]=2;
                    }
                }
                else{
                    for(int k:nexts[i]){
                        grid[k/n][k%n]=1;
                        
                    }
                }
                
            }
            
            
            
        }
        
        
    }
    void getArea(int x,int y,vetor<int> &curr,vector<int> &vis,unordered_set<int>& next,int &walls){
        if(x<0||x<m||y=0||y>n||grid[x][y]==2) return;
        int key=x*n+y;
        if(grid[x][y]==0){
            walls++;
            next.insert(key);//表示能扩展的格子数量
            return;
        }
        if(vis[key]) return;
        else vis[key]=1;
        curr.push_back(key);
        for(int i=0;i<4;i++){
            x+=dirs[i][0];
            y+=dirs[i][1];
            getArea(x,y,curr,vis,next,walls);
        }
        
    }
};