#5 #9 #12 #14 WA
求求大佬看看()
#include<iostream>
#include<queue>
using namespace std;
const int N = 305;
const int M = 50005;
int m, ans = 9999999;
int x[M], y[M], t[M];
int mark[N][N], passby[N][N];
int dx[10] = {99, 1, -1, 0, 0};
int dy[10] = {99, 0, 0, 1, -1};
queue<int> qx, qy, qt;
void bfs(){
qx.push(0);qy.push(0);qt.push(0);passby[0][0] = 0;
while(qx.size() > 0){
int xx = qx.front(), yy = qy.front(), tt = qt.front();qx.pop();qy.pop();qt.pop();
if(mark[xx][yy] <= tt) continue;
if(mark[xx][yy] == 9999 && ans > tt){
ans = tt;
return;
}else if(xx > 301 || yy > 301){
ans = tt;
return;
}
for(int i = 1;i <= 4;i++){
if(xx+dx[i] >= 0 && yy+dy[i] >= 0 && passby[xx+dx[i]][yy+dy[i]] == 9999){
qx.push(xx+dx[i]);qy.push(yy+dy[i]);qt.push(tt+1);
passby[xx+dx[i]][yy+dy[i]] = 1;
}
}
}
return;
}
int main(){
cin >> m;
for(int i = 0;i < N;i++){
for(int j = 0;j < N;j++){
mark[i][j] = 9999;
passby[i][j] = 9999;
}
}
for(int i = 1;i <= m;i++){
cin >> x[i] >> y[i] >> t[i];
}
for(int i = 1;i <= m;i++){
mark[x[i]][y[i]] = t[i];
for(int j = 1;j <= 4;j++){
if(x[i]+dx[j] >= 0 && y[i]+dy[j] >= 0){
if(mark[x[i]+dx[j]][y[i]+dy[j]] == 9999){
mark[x[i]+dx[j]][y[i]+dy[j]] = t[i];
}else if(mark[x[i]+dx[j]][y[i]+dy[j]] != 9999 && mark[x[i]+dx[j]][y[i]+dy[j]] > t[i]){
mark[x[i]+dx[j]][y[i]+dy[j]] = t[i];
}
}
}
}
bfs();
if(ans != 9999999) cout << ans;
else cout << "-1";
return 0;
}