Tanming_Hao_MC @ 2024-04-30 13:52:47
#include <algorithm>
#include <bitset>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ll long long
#define lf double
#define eps 1e-8
#define inf (1ll << 60)
#define pi 3.1415926535897932
#define _pb push_back
#define _mp make_pair
#define _1 first
#define _2 second
#define MAX_N 10000//int最大
#define maxn 1145//maxn做数组大小
using namespace std;
typedef long long LL;
struct coord {
int x, y;
};
queue<coord>Q;
int ans[maxn][maxn], death[maxn][maxn];
int wk[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};//方向函数
int main() {
int m, Ans = MAX_N;
memset(ans, -1, sizeof(ans));
memset(death, 0x7f, sizeof(death));
scanf("%d", &m);
for (int i = 1; i <= m; i++) {
int x, y, t;
scanf("%d %d %d", &x, &y, &t);
#define MIN(x,y,t) if(x>=0 && y>=0) death[x][y] = min(death[x][y],t)
MIN(x, y, t);
for (int k = 0; k < 4; k++)
MIN(x + wk[k][0], y + wk[k][1], t);
}
Q.push((coord) {
0, 0
});//压入地图
ans[0][0] = 0;
while (!Q.empty()) {
coord u = Q.front();
int ux = u.x, uy = u.y;
Q.pop();
for (int k = 0; k < 4; k++) {//Bessie走的路
int x = ux + wk[k][0], y = uy + wk[k][1];
if (x < 0 || y < 0 || ans[x][y] != -1 || ans[ux][uy] + 1 >= death[x][y])
continue;//剪枝
ans[x][y] = ans[ux][uy] + 1;
Q.push((coord){x,y});//将x,y(扩展的位置)压入栈
}
}
for(int i=0;i<=305;i++)
for(int j = 0; j <= 305; j++)//整个地图判断
if(death[i][j]> 1000 && ans[i][j] != -1)//只要不成立
Ans = min(Ans,ans[i][j]);
if(Ans ==MAX_N)
puts("-1");
else
printf("%d",Ans);
return 0;
}