RY111 @ 2024-07-06 10:56:20
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
//vector<PII> a;
const int maxn=310;
int t[maxn][maxn];
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
PII q[maxn*maxn];
int dist[maxn][maxn];
int bfs(int x,int y) {
int tt=0;
int hh=0;
q[tt++]= {x,y};
dist[x][y]=0;
while(hh<=tt)
{
auto t2=q[hh++];
for(int i=0; i<4; i++) {
int a=t2.first+dx[i];
int b=t2.second+dy[i];
if(a<0||b<0||a>300||b>300)
continue;
if(dist[a][b]!=0)
continue;
if(dist[t2.first][t2.second]+1>=t[a][b])
continue;
dist[a][b]=dist[t2.first][t2.second]+1;
q[tt++]={a,b};
if(t[a][b]>1e6)
return dist[a][b];
}
}
return -1;
}
int main() {
int m;
cin>>m;
memset(t,0x3f,sizeof t);
memset(dist,0x3f,sizeof dist);
while(m--)
{
int t1,x,y;
cin>>t1>>x>>y;
t[x][y]=min(t[x][y],t1);
for(int i=0;i<4;i++)
{
int a=x+dx[i];
int b=y+dy[i];
if(a<0||b<0||a>301||b>301)
continue;
else
t[a][b]=min(t[a][b],t1);
}
}
cout<<bfs(0,0);
return 0;
}