[LeetCode]Contain Virus

照着题目的描述来做就行。每一次扫一遍矩阵找出所有被感染的region，和对应的边界。然后每次找出下一天可以感染最多cell的区域，将其隔离。一直重复直到我们隔离所有感染区域或者整个世界被感染位置。具体细节：

1. 边界我们应该存什么?是把区域围起来的0，还是在和0相邻的1?这里我们仔细想一下就很好理解，我们显然应该存0，因为每一次我们要找的是下一天周围会被感染最多的region，那就是对应周围的0。1的话并不能准确表示，比如题目给出的例子：
   
   
   
   如果我们只记录1的话，边界的size会变成4。记录0的话可以正确反映下一轮会被感染的cells的多少。
2. 我们要建的墙的数量和边界的数量并不是一样的，比如下图：     
   
    蓝色的部分代表我们维护的边界，红色的部分代表我们要建的墙。我们可以看到数量分别为5和7，所以边界和墙我们要分别统计。统计墙的话，我们只要知道如果我们可以从value为1的任意一个方向到达value为0的cell，我们就需要建一堵墙。

假设输入矩阵大小为r * c，空间复杂度O(r * c)，时间复杂度最坏O(r^2 * c^2)，我们每次最多扫两次矩阵，迭代次数不会超过r * c次。代码如下：

	class Solution {
	public:
	int containVirus(vector<vector<int>>& grid) {
	int n = grid.size(), m = n? grid[0].size(): 0, walls = 0;
	while(true)
	{
	//Get information of all regions
	for(int i = 0; i < n; ++i)
	{
	for(int j = 0; j < m; ++j)
	{
	if(grid[i][j] == 1 && visited.find(i * m + j) == visited.end())
	{
	components.push_back(unordered_set<int>());
	frontiers.push_back(unordered_set<int>());
	perimeters.push_back(0);
	dfs(grid, i, j);
	}
	}
	}
	//find the region we need to block
	int idx = -1, len = components.size();
	for(int i = 0; i < len; ++i)
	{
	if(idx == -1 || frontiers[idx].size() < frontiers[i].size())
	idx = i;
	}
	//if all cells are affected, we return walls we built
	if(idx == -1)break;
	//update the wall we need to build, which equals to permeter
	walls += perimeters[idx];
	//flip blocked region to -1 and update all new affect cells
	for(auto& cell : components[idx])
	grid[cell / m][cell % m] = -1;
	for(int i = 0; i < len; ++i)
	{
	if(i == idx)continue;
	for(auto& cell : frontiers[i])
	grid[cell / m][cell % m] = 1;
	}
	//reset all data structure
	components.clear();
	frontiers.clear();
	perimeters.clear();
	visited.clear();
	}
	return walls;
	}
	private:
	vector<unordered_set<int>> components, frontiers;//store 0s instead of 1s
	vector<int> perimeters;//walls to add
	unordered_set<int> visited;
	void dfs(vector<vector<int>>& grid, int i, int j)
	{
	int n = grid.size(), m = n? grid[0].size(): 0;
	pair<int, int> dirs[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	int key = i * m + j;
	visited.insert(key);
	int len = components.size();
	components[len - 1].insert(key);
	for(auto& dir : dirs)
	{
	int x = i + dir.first, y = j + dir.second;
	if(x < n && x >= 0 && y >= 0 && y < m)
	{
	if(grid[x][y] == 1 && visited.find(x * m + y) == visited.end())
	dfs(grid, x, y);
	else if(grid[x][y] == 0)
	{
	//every time we can reach 0 from a 1, we need to add a wall there
	//perimeter is not the same as froniter size
	++perimeters[len - 1];
	frontiers[len - 1].insert(x * m + y);
	}
	}
	}
	}
	};

view raw Contain Virus.cpp hosted with ❤ by GitHub