Ay2024_4202yA @ 2024-12-17 18:45:20
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+5;
struct point{
int x,y,step;
};
int dx[]={0,0,-1,1};
int dy[]={1,-1,0,0};
int m;
int f[305][305];
int vis[305][305];
queue<point> q;
int main(){
for(int i=0;i<=300;i++){
for(int j=0;j<=300;j++){
f[i][j]=1e9;
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
f[a][b]=min(c,f[a][b]);
for(int j=0;j<4;j++){
if(a+dx[j]<0||b+dy[j]<0)continue;
f[a+dx[j]][b+dy[j]]=min(f[a+dx[j]][b+dy[j]],f[a][b]);
}
}/*
for(int i=0;i<=6;i++){
for(int j=0;j<=6;j++){
cout<<setw(10)<<f[i][j]<<' ';
}
cout<<endl;
}*/
point s;
s.x=0;s.y=0;s.step=0;
q.push(s);
while(!q.empty()){
point n=q.front();
q.pop();
vis[n.x][n.y]=true;
if(f[n.x][n.y]==1e9){
cout<<n.step<<endl;
return 0;
}if(f[n.x][n.y]<=n.step){
continue;
}
//cout<<n.x<<' '<<n.y<<' '<<n.step<<"\n";
for(int i=0;i<4;i++){
int nx=n.x+dx[i];
int ny=n.y+dy[i];
if(nx<0||ny<0||vis[nx][ny])continue;
point d;
d.x=nx;d.y=ny;d.step=n.step+1;
q.push(d);
}
}cout<<-1<<endl;
return 0;
}