LC 749. 隔离病毒

用时：2h 5m
初看以为门的数量=扩散数量。后来跑测试发现，可能扩散数量会有重和。所以门的数量>=扩散数量。优化的话，可以省去expand的bfs，一次bfs，记录当前和max的扩散量和已有量

class Solution {
public:
	int doorNumber = 0;
	enum InfectedType
	{
		clean,
		isInfecting,
		blocked,
		willInfect,
	};
	int containVirus(vector<vector<int>>& isInfected) {
		int maxTotalOutBlock = -1;
		int answer = 0;
		while (maxTotalOutBlock != 0) {
			auto [maxTotalOutBlockIn, answerPoints] =ContainVirusRecurrence(isInfected);
			maxTotalOutBlock = maxTotalOutBlockIn.second;
			/*cout << "x=" << maxTotalOutBlock << endl;
			for (int i = 0; i < isInfected.size(); i++)
			{
				for (int j = 0; j < isInfected[0].size(); j++)
				{
					cout << isInfected[i][j];
				}
				cout << endl;
			}*/
			answer += maxTotalOutBlock;
			SetInfectedToNextStage(isInfected,answerPoints);
			Expand(isInfected, answerPoints);
			
		}
		return answer;
	}
	void Expand(vector<vector<int>>& isInfected, vector<pair<int, int>>answerPoints) {
		for (int i = 0; i < isInfected.size(); i++)
		{
			for (int j = 0; j < isInfected[0].size(); j++)
			{
				if (isInfected[i][j] == InfectedType::isInfecting) {
					auto StartBfs = [&]() {
						vector<vector<bool>>isBlockVisited(isInfected.size(), vector<bool>(isInfected[0].size(), false));
						queue<pair<int, int>>bfsQueue;
						vector<pair<int, int>> directions = { {1,0},{-1,0},{0,1},{0,-1} };
						vector<pair<int, int>>point;
						int totalOutBlock = 0, doorNeeded = 0;
						bfsQueue.push({ i,j });
						isBlockVisited[i][j] = true;
						while (bfsQueue.empty() == false)
						{
							point.push_back(bfsQueue.front());
							auto [wi, wj] = bfsQueue.front();
							bfsQueue.pop();
							for (int k = 0; k < directions.size(); k++)
							{
								int nextI = wi + directions[k].first;
								int nextJ = wj + directions[k].second;
								if (nextI < isInfected.size() && nextJ < isInfected[0].size()
									&& nextI >= 0 && nextJ >= 0) {
									if (isBlockVisited[nextI][nextJ])continue;
									isBlockVisited[nextI][nextJ] = true;
									if (isInfected[nextI][nextJ] == InfectedType::clean) {
										isInfected[nextI][nextJ] = InfectedType::willInfect;
									}
									else  if (isInfected[nextI][nextJ] == InfectedType::isInfecting) {
										bfsQueue.push({ nextI,nextJ });
									}
								}
							}
						}
						return pair<pair<int, int>, vector<pair<int, int>>>{ {totalOutBlock, doorNeeded}, point };
					};
					StartBfs();
				}
			}
		}
		for (int i = 0; i < isInfected.size(); i++)
		{
			for (int j = 0; j < isInfected[0].size(); j++)
			{
				if(isInfected[i][j]==InfectedType::willInfect)
				isInfected[i][j] = InfectedType::isInfecting;
			}
		}
	}
	void SetInfectedToNextStage(vector<vector<int>>& isInfected, vector<pair<int, int>>answerPoints) {
		for (int i = 0; i < answerPoints.size(); i++)
		{
			isInfected[answerPoints[i].first][answerPoints[i].second] = InfectedType::blocked;
		}
	}
	pair<pair<int,int>,vector<pair<int,int>>> ContainVirusRecurrence(vector<vector<int>>& isInfected) {
		int maxTotalOutBlock = 0,doorNumber=0;
		vector<pair<int, int>>answerPoints;
		vector<vector<bool>>isInfectedBlockVisited(isInfected.size(), vector<bool>(isInfected[0].size(), false));
		for (int i = 0; i < isInfected.size(); i++)
		{
			for (int j = 0; j < isInfected[0].size(); j++)
			{
				if (isInfected[i][j]==InfectedType::isInfecting&& isInfectedBlockVisited[i][j]==false) {
					auto StartBfs = [&]() {
						queue<pair<int, int>>bfsQueue;
						vector<pair<int, int>> directions = { {1,0},{-1,0},{0,1},{0,-1} };
						vector<pair<int, int>>point;
						vector<vector<bool>>isBlockVisited(isInfected.size(), vector<bool>(isInfected[0].size(), false));
						int totalOutBlock = 0,doorNeeded=0;
						bfsQueue.push({ i,j });
						isBlockVisited[i][j] = true;
						while (bfsQueue.empty() == false)
						{
							point.push_back(bfsQueue.front());
							auto [wi, wj] = bfsQueue.front();
							isInfectedBlockVisited[wi][wj] = true;
							bfsQueue.pop();
							for (int k = 0; k < directions.size(); k++)
							{
								int nextI = wi + directions[k].first;
								int nextJ = wj + directions[k].second;
								//cout <<"x =" << nextI << ' ' << nextJ << endl;
								if (nextI < isInfected.size() && nextJ < isInfected[0].size()
									&& nextI>=0 && nextJ>=0) {
									//cout << nextI << ' ' << nextJ << endl;
									if (isInfected[nextI][nextJ] == InfectedType::clean) {
										//cout << "s =" << nextI << ' ' << nextJ << endl;
										++doorNeeded;
									}
									if (isBlockVisited[nextI][nextJ])continue;
									isBlockVisited[nextI][nextJ] = true;
									if (isInfected[nextI][nextJ] == InfectedType::clean) {
										++totalOutBlock;
									}
									else  if (isInfected[nextI][nextJ] == InfectedType::isInfecting) {
										bfsQueue.push({ nextI,nextJ });
									}
								}
							}
						}
						return pair<pair<int, int>, vector<pair<int, int>>>{ {totalOutBlock, doorNeeded}, point };
					};
					auto [oneBlockNeed,tempAnswerPoints] = StartBfs();
					/*cout << "xxx=" << oneBlockNeed.first << endl;
					cout <<"xjx="<< i<<' '<<j << endl;*/
					if (oneBlockNeed.first > maxTotalOutBlock) {

						maxTotalOutBlock = oneBlockNeed.first;
						answerPoints.clear();
						answerPoints = tempAnswerPoints;
						doorNumber = oneBlockNeed.second;
					}
				}
			}
		}

		return { {maxTotalOutBlock ,doorNumber},answerPoints };
		//30m+ 1h 20 m +15m=2H 5M
	}
};