Fryderyk_Chopin @ 2024-03-08 13:12:41
总是输出-1。其他一切正常。
#include<bits/stdc++.h>
using namespace std;
int n,d1[5]={0,1,-1,0,0},d2[5]={0,0,0,1,-1};
int ax,ay;
int dis[1010][1010];
bool vis[1010][1010];
struct boom {
int x,
y,
t;
}a[100010];
queue<boom>s;
bool check1(int x,int y,int t){
return x>=0 && y>=0 && x<=1009 && y<=1009;
}
bool check2(int x,int y,int t){
return x>=0 && y>=0 && x<=1009 && y<=1009 && dis[x][y]>t && !vis[x][y];
}
void bfs(int x,int y,int t){
int ax,ay,at,bx,by,bt;
vis[0][0]=1;
s.push((boom){0,0,0});
while(!s.empty()){
ax=s.front().x;ay=s.front().y;at=s.front().t;s.pop();
if(dis[ax][ay]==0){
cout<<at;
exit(0);
}
for(int i=1;i<=4;i++){
bx=ax+d1[i];by=ay+d2[i];bt=at+1;
if(check2(bx,by,bt)){
s.push((boom){bx,by,bt});
vis[bx][by]=1;
}
}
}
cout<<-1;
exit(0);
}
int main(){
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y>>a[i].t;
for(int j=0;j<=4;j++){
ax=a[i].x+d1[j];ay=a[i].y+d2[j];
if(check1(ax,ay,a[i].t)){
dis[ax][ay]=a[i].t;
}
}
}
bfs(0,0,0);
return 0;
}