# 749. 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:

1. The number of rows and columns of `grid` will each be in the range `[1, 50]`.
2. Each `grid[i][j]` will be either `0` or `1`.
3. Throughout the described process, there is always a contiguous viral region that will infect strictly moreuncontaminated squares in the next round.

``````class Solution {
public:
int containVirus(vector<vector<int>>& grid) {
int res = 0, m = grid.size(), n = grid[0].size();
vector<vector<int>> dirs{{-1,0},{0,1},{1,0},{0,-1}};
while (true) {
unordered_set<int> visited;
vector<vector<vector<int>>> all;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (grid[i][j] == 1 && !visited.count(i * n + j)) {
queue<int> q{{i * n + j}};
vector<int> virus{i * n + j};
vector<int> walls;
visited.insert(i * n + j);
while (!q.empty()) {
auto t = q.front(); q.pop();
for (auto dir : dirs) {
int x = (t / n) + dir[0], y = (t % n) + dir[1];
if (x < 0 || x >= m || y < 0 || y >= n || visited.count(x * n + y)) continue;
if (grid[x][y] == -1) continue;
else if (grid[x][y] == 0) walls.push_back(x * n + y);
else if (grid[x][y] == 1) {
visited.insert(x * n + y);
virus.push_back(x * n + y);
q.push(x * n + y);
}
}
}
unordered_set<int> s(walls.begin(), walls.end());
vector<int> cells{(int)s.size()};
all.push_back({cells ,walls, virus});
}
}
}
if (all.empty()) break;
sort(all.begin(), all.end(), [](vector<vector<int>> &a, vector<vector<int>> &b) {return a[0][0] > b[0][0];});
for (int i = 0; i < all.size(); ++i) {
if (i == 0) {
vector<int> virus = all[0][2];
for (int idx : virus) grid[idx / n][idx % n] = -1;
res += all[0][1].size();
} else {
vector<int> wall = all[i][1];
for (int idx : wall) grid[idx / n][idx % n] = 1;
}
}
}
return res;
}
};
``````

https://discuss.leetcode.com/topic/114208/c-dfs-12ms

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation