JunBuJian @ 2022-03-17 09:44:27
#include<iostream>
#include<queue>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 410;
int t[N][N],d[N][N];
bool st[N][N];
int n;
int dx[] = {1,-1,0,0},dy[] = {0,0,1,-1};
int bfs()
{
queue<PII> q;
q.push({0,0});
memset(d,-1,sizeof d);
d[0][0] = 0;
while(q.size())
{
auto h = q.front();
q.pop();
for(int i = 0;i < 4;i ++)
{
int x = h.x + dx[i];
int y = h.y + dy[i];
if(x < 0 || y < 0 || x > 300 || y > 300) continue;// 边界
if(t[x][y] != 10000 && d[h.x][h.y] + 1 >= t[x][y]) continue;
d[x][y] = d[h.x][h.y] + 1;
if(t[x][y] == 10000) return d[x][y];
q.push({x,y});
}
}
return -1;
}
int main()
{
cin >> n;
for(int i = 0;i <= 300;i ++)
for(int j = 0;j <= 300;j ++)
t[i][j] = 10000;
int a,b,m;
while(n --)
{
cin >> a >> b >> m;
if(st[a][b]) t[a][b] = min(t[a][b],m);
else
{
t[a][b] = m;
st[a][b] = true;
}
//预处理陨石掉落时间和范围
for(int i = 0;i < 4;i ++)
{
int x = a + dx[i];
int y = b + dy[i];
if(x < 0 || y < 0 || x > 300 || y > 300) continue;
if(st[x][y]) t[x][y] = min(t[x][y],m);
else
{
t[x][y] = m;
st[x][y] = true;
}
}
}
cout << bfs() << endl;
}