EmissaryD @ 2022-03-11 17:32:08
#include <stdio.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <queue>
#include <math.h>
#include <iostream>
using namespace std;
#define MAXN 301
#define Inf 0x3f3f3f3f
int f[MAXN][MAXN];
bool vis[MAXN][MAXN];
int m[MAXN][MAXN];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};
queue< pair<int, int>> q;
bool ans = false;
int main(){
memset(f, -1, sizeof(f));
memset(vis, false, sizeof(vis));
memset(m, Inf, sizeof(m));
int n;
scanf("%d", &n);
while(n--){
int i, j, t;
scanf("%d%d%d", &i, &j, &t);
if( m[i][j] > t ){
m[i][j] = t;
}
for(int k = 0;k <= 3;k++){
if((i + dx[k]) < 0 || (i + dx[k]) >= MAXN || (j + dy[k]) < 0 || (j + dy[k]) >= MAXN){
continue;
}
if( m[i+dx[k]][j+dy[k]] < t ){
continue;
}
m[i+dx[k]][j+dy[k]] = t;
}
}
// for(int i = 0; i <= 5; i++){
// for(int j = 0;j <= 5;j++){
// printf("%d ", m[i][j]);
// }
// printf("\n");
// }
f[0][0] = 0;
vis[0][0] = true;
int finx,finy;
q.push(make_pair(0, 0));
while(!q.empty()){
int xx =q.front().first, yy = q.front().second;
finx = xx;
finy = yy;
q.pop();
if(m[xx][yy] == Inf){
ans = true;
break;
}
for(int i = 0;i <= 3;i++){
int u = xx + dx[i], v = yy + dy[i];
if(u < 0 || u >= MAXN || v < 0 || v >= MAXN || vis[u][v]){
continue;
}
if(f[xx][yy] >= m[u][v] - 1){
continue;
}
vis[u][v] = true;
f[u][v] = f[xx][yy] + 1;
q.push(make_pair(u, v));
}
}
// for(int i = 0;i <= 5;i++){
// for(int j = 0;j <= 5;j++){
// printf("%d ", f[i][j]);
// }
// printf("\n");
// }
if(ans = true){
printf("%d", f[finx][finy]);
}else{
printf("-1");
}
return 0;
}