D.小L的扩展

题意: 有n×m的矩阵，有a个格子是染黑的，并在每个单位时间往外四个方向扩散。有b个格子是蓝墨水，他会在时间刻变白，在变白之前他不会被染黑，求整个矩阵全部染黑的时间。（蓝墨水变白的判定在染黑判定之前，换句话说如果蓝墨水旁边有个染黑的格子，假设蓝墨水到第5s变白，那他会被旁边的染黑格子在第5s染黑。）

知识点: BFS，图论

思路: 把每个染黑的格子放入优先队列里边BFS，并初始化染黑的格子为0，接着每次BFS都等于前一个格子+1，来模拟他的时间，当遇到蓝色墨水时，则等于max(下一秒,蓝墨水变白的时刻)，然后用一个maxn变量，在每次格子数值改变时记录下最大的时间就可以了。（不会BFS和优先队列的建议去看看基础BFS题目和优先队列题目，然后再来做这题。）

同时优先队列我还是选用的三元组，设置第一个元素为达到当前格子的时间，来实现时间早的先BFS，这样可以避免出现普通BFS时遇到一坨蓝色的，然后我BFS找到这个蓝色之后，把他设置成max(下一秒,蓝墨水变白的时刻)，然后直接BFS到下一个蓝色方块，直接继承上一个蓝色方块+1，但是有其他黑色方块直接染到这个方块时间更少，举个例子。

设黑色为0，白色为-1，蓝色为变成白色的时刻t

 +0 -1 -1
-1  7  -1
-1  3 -1  
普通BFS第一轮（按照上右下左的顺序）
+0  1 -1
 1  7 -1
-1  3 -1  
第二轮
+0  1  2
 1  7  3
 2  8 -1  //就出现问题了
 
 而在优先对列下加入了时间排序，7会直接排到最后，就会先等2,3那些先BFS完了最后到他

参考代码:

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define PLL pair<ll,ll>
#define PII pair<int,int>
#define endl '\n'
using namespace std;
const int m=998244353;
const int mod=1e9+7;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool judg(int nex,int ney,int n,int m)
{
	return (nex>=0&&nex<n&&ney>=0&&ney<m);
}
int main()
{
	cin.tie(0),cout.tie(0),ios::sync_with_stdio(0);
	int n,m,a,b,maxn=-1;
	cin >> n >> m >> a >> b;
	vector<vector<int>> mp(n,vector<int>(m,-1));
	vector<vector<bool>> v(n,vector<bool>(m,0));
	priority_queue<pair<int,PII>,vector<pair<int,PII>>,greater<pair<int,PII>>> pq;
	for(int i=0;i<a;i++){
		int x,y;
		cin >> x >> y;
		x--,y--;
		mp[x][y]=0;
		pq.push({mp[x][y],{x,y}});
		v[x][y]=1;
	}
	for(int i=0;i<b;i++){
		int x,y,t;
		cin >> x >> y >> t;
		x--,y--;
		mp[x][y]=t;
	}
	while(!pq.empty()){
		PII top=pq.top().second;
		int t=pq.top().first;
		pq.pop();
		for(int i=0;i<4;i++){
			int nex=top.first+dx[i],ney=top.second+dy[i];
			if(judg(nex,ney,n,m)&&!v[nex][ney]){
				if(mp[nex][ney]==-1){
					mp[nex][ney]=t+1;
					pq.push({mp[nex][ney],{nex,ney}});
				}
				else{
					mp[nex][ney]=max(t+1,mp[nex][ney]);
					pq.push({mp[nex][ney],{nex,ney}});
				}
				v[nex][ney]=1;
				maxn=max(mp[nex][ney],maxn);
			}
		}
	}
	cout << maxn;
	return 0;
}