tall_buildin @ 2024-10-02 17:33:30
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {1,0,-1,0},dy[4]= {0,1,0,-1};
int t[305][305];
bool vis[305][305];
bool flag[305][305];
int m;
struct point{int x;int y;int time;};
int bfs(int x,int y,int time){
queue<point>q;q.push({x,y,time});
while(!q.empty()){
point now = q.front();q.pop();
if (vis[now.x][now.y] == 1){
return now.time;
}
for (int i = 0;i<4;i++){
int nx = now.x+dx[i],ny = now.y+dy[i];
if (nx<0 || ny<0 || nx>300|| ny>300) continue;
if (t[nx][ny]>now.time+1&&flag[nx][ny] == 0){
flag[nx][ny] = 1;
q.push({nx,ny,now.time+1});
}
}
}
return -1;
}
void bj(int x,int y,int time){
vis[x][y] = 0;t[x][y] = time;
for (int i = 0;i<4;i++){
if (x+dx[i]<0 || y+dy[i]<0 ) continue;
vis[x+dx[i]][y+dy[i]] = 0;
t[x+dx[i]][y+dy[i]] = time;
}
}
signed main(){
memset(flag,0,sizeof(flag));
memset(t,0x3f,sizeof(t));
memset(vis,1,sizeof(vis));
cin>>m;
for (int i = 1;i<=m;i++){
int x,y,time;cin>>x>>y>>time;
time = min(time,t[x][y]);
bj(x,y,time);
}
cout<<bfs(0,0,0);
return 0;
}
/*
23
2 5 10
1 3 5
5 3 12
3 3 9
1 8 7
8 4 15
2 3 7
0 0 2
6 7 10
4 4 10
3 7 7
8 5 13
0 4 9
2 6 8
0 2 4
6 4 12
0 6 7
4 2 10
1 4 7
4 6 10
5 5 12
6 5 14
2 1 2
13
*/