leetcode 困难题 749. Contain Virus 隔离病毒

Problem: 749. Contain Virus 隔离病毒

解题过程

拿到每个区域内影响cell最多的那个，cell=0的不能重复，不能用sum的最大值，而是te.size()的最大值，然后最大的区域置-1，继续感染的，继续统计最大的那个区域

Code

class Solution { public: int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int containVirus(vector<vector<int>>& isInfected) { int m = isInfected.size(), n = isInfected[0].size(); int x, y, count = 0; while(true) { vector<vector<bool>> status(m, vector<bool>(n, false)); vector<vector<pair<int, int>>> collect; int maxeffect = 0, id = INT_MIN; int mxmx = INT_MIN; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if( isInfected[i][j]==1 && status[i][j]==false ) { queue<pair<int, int>> qe; qe.push({i, j}); collect.push_back({}); status[i][j] = true; pair<int, int> pr; int sum = 0; unordered_set<int> te; while(!qe.empty()) { pr = qe.front(); collect.back().push_back(pr); qe.pop(); for(int k = 0; k < 4; k++) { x = pr.first + dir[k][0]; y = pr.second + dir[k][1]; if( x<0 || y<0 || x>=m || y>=n || status[x][y]==true || isInfected[x][y] == -1) continue; if(isInfected[x][y]==0) { sum++; te.insert((x<<20) + y); continue; } else if(isInfected[x][y]==1) { status[x][y] = true; qe.push({x, y}); } } } if(mxmx < (int)te.size()) { maxeffect = sum; mxmx = te.size(); id = collect.size() - 1; } if(sum == 0) { collect.pop_back(); } } } } if(collect.size() == 0) break; count += maxeffect; if(id != INT_MIN) { for(int j = 0; j < collect[id].size(); j++) { isInfected[collect[id][j].first][collect[id][j].second] = -1; } collect.erase(collect.begin() + id); } if(collect.size() == 0) break; for(int j = 0; j < collect.size(); j++) { for(int i = 0; i < collect[j].size(); i++) { for(int k = 0; k < 4; k++) { x = collect[j][i].first + dir[k][0]; y = collect[j][i].second + dir[k][1]; if( x<0 || y<0 || x>=m || y>=n) continue; if(isInfected[x][y]==0) { isInfected[x][y] = 1; } } } } } return count; } };