染色+排序+记忆化

#include<iostream>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
int fx[]={0,1,0,-1};
int fy[]={1,0,-1,0};
int f[305][305];
int k;
bool vis[305][305];
struct node{
    int x,y,t;
};
struct sb{
    int x,y,t;
}a[50010];
bool cmp(sb a,sb b){
    return a.t<b.t;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y>>a[i].t;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        k=a[i].t;
        if(f[a[i].x][a[i].y]==-1) f[a[i].x][a[i].y]=k;
        
        for(int j=0;j<4;j++){
            int tx=a[i].x+fx[j];
            int ty=a[i].y+fy[j];
            if(tx>=0&&ty>=0&&f[tx][ty]==-1){
                f[tx][ty]=k;
            }
        }
    }
//    for(int i=0;i<=10;i++){
//            for(int j=0;j<=10;j++){
//                cout<<f[i][j]<<" ";
//            }
//            cout<<endl;
//        }
    queue<node>q;
    q.push((node){0,0,0});
    vis[0][0]=1;
    while(!q.empty()){
        int x=q.front().x;
        int y=q.front().y;
        int t=q.front().t;
//        cout<<x<<" "<<y<<" "<<t<<endl;
        if(f[x][y]==-1){
            cout<<t;
            return 0;
        }
        if(f[x][y]>t){//不在这秒
            for(int i=0;i<4;i++){
                int tx=x+fx[i];
                int ty=y+fy[i];
                if(tx>=0&&ty>=0&&!vis[tx][ty]&&(f[tx][ty]>t+1||f[tx][ty]==-1)){
                    q.push((node){tx,ty,q.front().t+1});
                    vis[tx][ty]=1;
                }
            }
        }
        q.pop();
    }
    cout<<-1;
    return 0;
}