Liyuqiao11 @ 2023-01-12 18:03:26
#include<bits/stdc++.h>
using namespace std;
long long int m,vis[1010][1010],dx[4]={1,-1,0,0},dy[4]={0,0,1,-1},a[1010][1010];
struct N{
int cnt;
int x;
int y;
};
int bfs(int x,int y){
queue<N> q;
q.push((N){0,x,y});
vis[x][y]=1;
while(!q.empty()){
int u=q.front().x,v=q.front().y,dc=q.front().cnt;
q.pop();
for(int i=0;i<4;i++){
int nx=u+dx[i],ny=v+dy[i];
if(nx>=0&&ny>=0&&vis[nx][ny]==0&&(a[nx][ny]>dc+1||a[nx][ny]==-1)){
if(a[nx][ny]==-1){
return dc+1;
}
q.push((N){dc+1,nx,ny});
vis[nx][ny]=1;
}
}
}
return -1;
}
int main(){
cin>>m;
memset(a,-1,sizeof(a));
for(int i=1;i<=m;i++){
long long int d,c,yq;
cin>>d>>c;
cin>>yq;
if(a[d][c]==-1){
a[d][c]=yq;
}
else{
a[d][c]=min(a[d][c],yq);
}
if(a[d+1][c]==-1){
a[d+1][c]=a[d][c];
}
else{
a[d+1][c]=min(a[d+1][c],a[d][c]);
}
if(a[d][c+1]==-1){
a[d][c+1]=a[d][c];
}
else{
a[d][c+1]=min(a[d][c+1],a[d][c]);
}
if(d>=1){
if(a[d-1][c]==-1){
a[d-1][c]=a[d][c];
}
else{
a[d-1][c]=min(a[d-1][c],a[d][c]);
}
}
if(c>=1){
if(a[d][c-1]==-1){
a[d][c-1]=a[d][c];
}
else{
a[d][c-1]=min(a[d][c-1],a[d][c]);
}
}
}
cout<<bfs(0,0);
return 0;
}
by Liyuqiao11 @ 2023-01-12 18:42:29
此贴结