题解 | #小L的扩展#

D题题解:

每个格子被黑格子覆盖的时间，等于从最近的初始黑格子扩散到它的时间； 但蓝格子有 “保护期”,只有当扩散时间>保护期 之后才能被覆盖，因此该格子的实际变黑时间为 max(扩散时间,t保护期）

初始黑格子的变黑时间为 0，加入优先队列； 每次取出当前最早变黑的格子，向四邻扩散；

对每个邻格，计算它的变黑时间（当前格子时间，蓝格子保护期）； 最终所有格子变黑时间的最大值，就是整张纸被完全染黑的时刻。

代码演示：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define endl '\n'
#define PI3 array<long long,3>
const int N = 1000000005;
int dx[4]={0,-1,0,1};
int dy[4]={-1,0,1,0};

priority_queue<PI3,vector<PI3>,greater<PI3>>q;
void solve(){
	int n,m,a,b,x,y,t,sum=0;
	cin>>n>>m>>a>>b;
	vector<vector<int>>arr(n,vector<int>(m,N));
	vector<vector<int>>brr(n,vector<int>(m,0));
	for(int i=1;i<=a;i++){
		cin>>x>>y;
		arr[x-1][y-1]=0;
		q.push({0,x-1,y-1});
	}
	for(int i=1;i<=b;i++){
		cin>>x>>y>>t;
		brr[x-1][y-1]=t;
	}
	while(!q.empty()){
		t=q.top()[0];
		x=q.top()[1];
		y=q.top()[2];
		q.pop();
		sum=max(sum,t);
		for(int i=0;i<4;i++){
			int px=x+dx[i];
			int py=y+dy[i];
			if(px<0||px>=n||py<0||py>=m||arr[px][py]!=N) continue;
            arr[px][py]=max(brr[px][py],t+1);
            q.push({arr[px][py],px,py});
			
		}
	}
	
	cout<<sum<<endl;
}

signed main(){
	ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	while(T--){
		solve();
	}
	return 0;
}