7分求助5~

P2895 [USACO08FEB] Meteor Shower S

FYH666666 @ 2024-08-20 17:07:57

#include<bits/stdc++.h>
using namespace std;
int m,sav[305][305],f[305][305],tim=0,sum=1;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
struct ys{
    int lx,ly,t;
}lx[5005],lx2;
queue<ys> q;
struct dl{
    int x,y;
}nw,nxt;
queue<dl> z;
bool cmp(ys a,ys b){
    return a.t<b.t;
}
int main(){
    scanf("%d",&m);
    for(int i=1;i<=m;i++) scanf("%d%d%d",&lx[i].lx,&lx[i].ly,&lx[i].t);
    sort(lx+1,lx+m+1,cmp);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=4;j++){
            int xxx=lx[i].lx+dx[j],yyy=lx[i].ly+dy[j];
            if(xxx>=0&&yyy>=0) sav[xxx][yyy]=1;
        }
        sav[lx[i].lx][lx[i].ly]=1;
        lx2.lx=lx[i].lx;
        lx2.ly=lx[i].ly;
        lx2.t=lx[i].t;
        q.push(lx2);
    }
    nw.x=0;
    nw.y=0;
    z.push(nw);
    f[0][0]=1;
    if(sav[0][0]==0){
        printf("0");
        return 0;
    }
    while(!z.empty()){
        nw=z.front();
        z.pop();
        for(int i=1;i<=4;i++){
            int xx=nw.x+dx[i],yy=nw.y+dy[i];
            if(xx>=0&&yy>=0&&f[xx][yy]==0){
                f[xx][yy]=f[nw.x][nw.y]+1;
                nxt.x=xx;
                nxt.y=yy;
                z.push(nxt);
                if(f[xx][yy]>sum){
                    sum++;
                    tim++;
                    while(q.front().t<=tim){
                        f[q.front().lx][q.front().ly]=1;
                        q.pop();
                    } 
                }
                if(!sav[xx][yy]){
                    printf("%d",tim);
                    return 0;
                }   
            }
        }
    }
    printf("-1");
    return 0;
}

by qqq123456qqq @ 2024-08-21 09:30:42

太复杂


|