qqq123456qqq @ 2024-08-21 09:51:47
#include<stdio.h>
#include<queue>
using namespace std;
struct qqt{
int x,y;
}fi,la;
int a,lx[500005],ly[500005],lt[500005],f[5005][5005],p=1,o;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
queue<qqt> q;
int main(){
scanf("%d",&a);
for(int i=1;i<=a;i++) scanf("%d%d%d",&lx[i],&ly[i],<[i]);
fi.x=0;
fi.y=0;
f[0][0]=1;
q.push(fi);
while(!q.empty()){
fi=q.front();
q.pop();
for(int i=0;i<4;i++){
int xx=fi.x+dx[i],yy=fi.y+dy[i];
if(xx>301||yy>301){
printf("%d",p);
return 0;
}
if(f[xx][yy]==0){
f[xx][yy]=f[fi.x][fi.y]+1;
la.x=xx;
la.y=yy;
q.push(la);
if(f[xx][yy]>p){
p++;
for(int j=1;j<=a;j++){
if(lt[j]==p){
o++;
f[lx[j]][ly[j]]=-1;
for(int k=0;k<4;k++){
f[lx[j]+dx[k]][ly[j]+dy[k]]=-1;
}
}
if(o==a){
printf("%d",p);
return 0;
}
}
}
}
}
}
printf("-1");
return 0;
}