题解 | #D#

题目

输入

输出

思路

对于每个色块，它都有位置和染色时间两个信息。所以可以用pair来储存黑色块信息，然后放入优先队列，以时间为key从小到大排序。

然后对最小的黑色块，向四个方向蔓延，同时更新染色时间。

特殊的蓝色块，则要比较它染色的时间，和题目给出的变色时间的大小，比题目时间大时才能放入优先队列。

对于色块的位置则可以转化为一维的数据，便于存储。

完整代码

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PII pair<ll,ll>
ll dx[4]={1,0,0,-1};
ll dy[4]={0,1,-1,0};

signed main(){
    ll n,m,a,b;
    cin>>n>>m>>a>>b;
    vector<ll> bk(n*m,-1);
    vector<ll> bu(n*m,-1);
    priority_queue<PII,vector<PII>,greater<PII>> pq;
    for(ll i=0;i<a;i++){
        ll x,y;
        cin>>x>>y;
        ll pos=(x-1)*m+y-1;
        bk[pos]=0;
        pq.push({0,pos});
    }
    for(ll i=0;i<b;i++){
        ll x,y,t;
        cin>>x>>y>>t;
        ll pos=(x-1)*m+y-1;
        bu[pos]=t;
    }
    ll ans=0;
    while(!pq.empty()){
        auto [t,pos]=pq.top();
        pq.pop();
        if(t>bk[pos]) continue;
        ans=max(ans,t);
        ll x0=pos/m;
        ll y0=pos%m;
        for(ll i=0;i<4;i++){
            ll x1=x0+dx[i];
            ll y1=y0+dy[i];
            if(x1>=0&&x1<n&&y1>=0&&y1<m){
                ll poss=x1*m+y1;
                ll cur=t+1;
                ll ne=max(bu[poss],cur);
                if(ne<bk[poss]||bk[poss]==-1){
                    bk[poss]=ne;
                    pq.push({bk[poss],poss});
                
                }

            }
        
        }
        
        
        
        
    }
    cout<<ans<<"\n";
return 0;
}