SUPERRYX @ 2021-08-19 12:30:46
#include <bits/stdc++.h>
using namespace std;
int n,a[1001][1001],x_,y_,t_,t[1001][1001];
bool vis[1001][1001];
int pd(int l){
if(l==-1) return 99999;
else return l;
}
queue<int> q1,q2;
//0,0,1,-1
//1,-1,0,0
int main(){
cin>>n;
for(int i=0;i<1000;i++)
for(int j=0;j<1000;j++)
t[i][j]=-1;
for(int i=1;i<=n;i++){
cin>>x_>>y_>>t_;
if( x_>=0 && y_>=0 && (t[x_][y_]==-1||t[x_][y_]>t_) ) t[x_][y_]=t_;
if( x_>=0 && y_+1>=0 && (t[x_][y_+1]==-1||t[x_][y_+1]>t_) ) t[x_][y_+1]=t_;
if( x_>=0 && y_-1>=0 && (t[x_][y_-1]==-1||t[x_][y_-1]>t_) ) t[x_][y_-1]=t_;
if( x_+1>=0 && y_>=0 && (t[x_+1][y_]==-1||t[x_+1][y_]>t_) ) t[x_+1][y_]=t_;
if( x_-1>=0 && y_>=0 && (t[x_-1][y_]==-1||t[x_-1][y_]>t_) ) t[x_-1][y_]=t_;
}
vis[0][0]=1;
q1.push(0);q2.push(0);
while(!q1.empty()){
int x=q1.front(),y=q2.front();
q1.pop();q2.pop();
int k=a[x][y]+1;
if (t[x][y]==-1){
cout<<k-1<<endl;
return 0;
}
if(!vis[x+1][y]&&k<pd(t[x+1][y])&&x+1>=0&&y>=0){
q1.push(x+1);q2.push(y);
vis[x+1][y]=1;
a[x+1][y]=k;
}
if(!vis[x][y+1]&&k<pd(t[x][y+1])&&x>=0&&y+1>=0){
q1.push(x);q2.push(y+1);
vis[x][y+1]=1;
a[x][y+1]=k;
}
if(!vis[x-1][y]&&k<pd(t[x-1][y])&&x-1>=0&&y>=0){
q1.push(x-1);q2.push(y);
vis[x-1][y]=1;
a[x-1][y]=k;
}
if(!vis[x][y-1]&&k<pd(a[x][y-1])&&x>=0&&y-1>=0){
q1.push(x);q2.push(y-1);
vis[x][y-1]=1;
a[x][y-1]=k;
}
}
cout<<-1<<endl;
return 0;
}
by SUPERRYX @ 2021-08-19 12:35:09
qwq