ylx0527 @ 2024-11-30 17:35:25
#include<bits/stdc++.h>
using namespace std;
int m;
struct note{
int x, y, t;
};
note a[100000];
int cnt = -1;
int dx[5] = {0, 0, 1, 0, -1};
int dy[5] = {0, 1, 0, -1, 0};
int flag[500][500];
int dt[500][500];
void bfs(int xx, int yy, int tt){
queue<note> q;
flag[xx][yy] = 1;
q.push((note){xx, yy, tt});
while(!q.empty()){
note to = q.front();
q.pop();
if(dt[to.x][to.y] == 1e9) {
cnt = to.t;
break;
}
for(int i = 1; i <= 4; i++){
int xxx = to.x+dx[i];
int yyy = to.y+dy[i];
if(xxx >= 0 && yyy >= 0 && !flag[xxx][yyy] && to.t+1 < dt[xxx][yyy]){
q.push((note){xxx, yyy, to.t+1});
// cout << xxx << " " << yyy << " " << to.t+1 << endl;
flag[xxx][yyy] = 1;
}
}
}
}
int main(){
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
cin>>m;
for(int i = 0; i <= 400; i++){
for(int j = 0; j <= 400; j++){
dt[i][j] = 1e9;
}
}
for(int i = 1; i <= m; i++){
cin >> a[i].x >> a[i].y >> a[i].t;
dt[a[i].x][a[i].y] = a[i].t;
for(int j = 1; j <= 4; j++){
dt[a[i].x+dx[j]][a[i].y+dy[j]] = a[i].t;
}
}
bfs(0, 0, 0);
cout << cnt;
return 0;
}