Jacky2009 @ 2021-08-28 15:03:50
#include<bits/stdc++.h>
using namespace std;
int hit[305][305];
int times[305][305];
struct point{
int x,y;
};
point fi[305][305];
int main(){
int n;
cin>>n;
memset(times,0,sizeof(times));
memset(hit,127,sizeof(hit));
// cout<<hit[0][0];
for(int i=0;i<n;i++){
int x,y,z;
cin>>x>>y>>z;
if(hit[x][y]>=z)hit[x][y]=z;
if(y-1>=0)if(hit[x][y-1]>=z)hit[x][y-1]=z;
if(x-1>=0)if(hit[x-1][y]>=z)hit[x-1][y]=z;
if(hit[x+1][y]>=z)hit[x+1][y]=z;
if(hit[x][y+1]>=z)hit[x][y+1]=z;
}
for(int i=0;i<305;i++){
for(int j=0;j<305;j++){
fi[i][j].x=i;
fi[i][j].y=j;
}
}
int g[4][2]={{1,0},{-1,0},{0,-1},{0,1}};
queue<point>q;
q.push(fi[0][0]);
while(!q.empty()){
point xy=q.front();
q.pop();
for(int i=0;i<4;i++){
int fx=xy.x+g[i][0],fy=xy.y+g[i][1];
if(fx>=0&&fy>=0&×[xy.x][xy.y]+1<hit[fx][fy]&&fx<301&&fy<301){
times[fx][fy]=times[xy.x][xy.y]+1;
q.push(fi[fx][fy]);
if(hit[fx][fy]==2139062143){
cout<<times[fx][fy];
return 0;
}
}
}
}
cout<<-1;
}
by osky123456 @ 2021-08-28 16:04:00
可以查一下有没有超内存,数据类型需不需要开long long(不开long long ,oi白学)
by osky123456 @ 2021-08-28 16:35:36
(个人感觉这个bfs应该先处理陨石……)