_Aurore_ @ 2022-03-22 17:44:44
#include<bits/stdc++.h>
using namespace std;
int head=0,tail=1;
int go[410][410];
int farm_use[410][410];
int farm_time[410][410];
int wei_x[4]={0,0,1,-1};
int wei_y[4]={-1,1,0,0};
struct stone{
int x,y,time;
}stone[50010];
struct queue{
int x,y;
}que[410*410];
int main(){
int input;
cin>>input;
for(int i=0;i<=310;i++){
for(int j=0;j<=310;j++){
farm_time[i][j]=1000000000;
}
}
for(int i=1;i<=input;i++){
cin>>stone[i].x>>stone[i].y>>stone[i].time;
farm_time[stone[i].x][stone[i].y]=stone[i].time;
for(int j=0;j<4;j++){
farm_time[stone[i].x+wei_x[j]][stone[i].y+wei_y[j]]=min(stone[i].time,farm_time[stone[i].x+wei_x[j]][stone[i].y+wei_y[j]]);
}
}
// for(int i=0;i<=10;i++){
// for(int j=0;j<=10;j++){
// if(farm_time[i][j]==10) cout<<farm_time[i][j]<<" ";
// else cout<<farm_time[i][j]<<" ";
// }
// cout<<endl;
// }
que[1].x=0;
que[1].y=0;
go[que[1].x][que[1].y]=0;
while(head<tail){
if(farm_time[que[head].x][que[head].y]==1000000000){
int go_now=go[que[head].x][que[head].y];
cout<<go_now;
return 0;
}
head++;
int go_now=go[que[head].x][que[head].y]+1;
for(int i=0;i<4;i++){
int x_now=que[head].x+wei_x[i];
int y_now=que[head].y+wei_y[i];
if(x_now>=0&&y_now>=0
&&farm_time[x_now][y_now]>go_now
&&farm_use[x_now][y_now]==0){
farm_use[x_now][y_now]=1;
tail++;
que[tail].x=x_now;
que[tail].y=y_now;
go[x_now][y_now]=go_now;
}
}
}
cout<<-1;
return 0;
}