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
太复杂