liyinqi005110 @ 2024-11-24 20:13:56
# include<bits/stdc++.h>
using namespace std;
const int N=305;
typedef pair<int,int> Pair;
int vis[N][N],bu[N][N],z[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,1,-1};
int M;
bool init(int x,int y){
return x<=N&&x>=0&&y<=N&&y>=0;
}
int main(){
cin>>M;
for(int i=0;i<=N;i++){
for(int j=0;j<=N;j++) bu[i][j]=1008;
}
memset(z,-1,sizeof(z));
for(int i=1;i<=M;i++){
int x,y,t;
cin>>x>>y>>t;
bu[x][y]=min(bu[x][y],t);
for(int j=0;j<4;j++){
if(init(x+dx[j],y+dy[j])){
bu[x+dx[j]][y+dy[j]]=min(bu[x+dx[j]][y+dy[j]],t);
}
}
}
vis[0][0]=1;
z[0][0]=0;
queue<Pair> pq;
pq.push({0,0});
int ans=-1;
while(pq.size()){
int cx=pq.front().first;
int cy=pq.front().second;
pq.pop();
int flag=0;
for(int i=0;i<4;i++){
int zx=cx+dx[i],zy=cy+dy[i];
if(init(zx,zy)&&vis[zx][zy]==0){
if(z[cx][cy]+1>=bu[zx][zy]) continue;
z[zx][zy]=z[cx][cy]+1;
vis[zx][zy]=1;
if(bu[zx][zy]==1008){
ans=z[zx][zy];
flag=1;
}
pq.push({zx,zy});
}
}
if(flag) break;
}
if(ans==-1)cout<<-1;
else cout<<ans;
}
######