冰之紫水晶 @ 2021-10-29 19:09:05
#include<bits/stdc++.h>
using namespace std;
#define MAXN 310
int ans[MAXN][MAXN],meteor[MAXN][MAXN];
struct coord{
int x,y;
};
queue<coord> Q;
int rage[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int main(){
int m;
cin>>m;
int t;
memset(meteor,0x7f,sizeof(meteor));
memset(ans,-1,sizeof(ans));
for(int i=0;i<m;i++){
coord temp;
cin>>temp.x>>temp.y>>t;
meteor[temp.x][temp.y]=t;
for(int j=0;j<4;j++){
if(temp.x+rage[j][0]>=0&&temp.x+rage[j][0]<=300&&temp.y+rage[j][1]>=0&&temp.y+rage[j][1]<=300){
if(meteor[temp.x+rage[j][0]][temp.y+rage[j][1]]>t){
meteor[temp.x+rage[j][0]][temp.y+rage[j][1]]=t;
}
}
}
}
ans[0][0]=0;
Q.push((coord){0,0});
while(!Q.empty()){
coord u=Q.front();
int ux=u.x,uy=u.y;
Q.pop();
for(int i=0;i<4;i++){
int x=ux+rage[i][0],y=uy+rage[i][1];
if(meteor[x][y]<=ans[ux][uy]+1||ans[x][y]!=-1||x<0||y<0||x>300||y>300){
continue;
}
ans[x][y]=ans[ux][uy]+1;
Q.push((coord){x,y});
}
}
/*for(int i=0;i<20;i++){
for(int j=0;j<20;j++){
if(meteor[i][j]>1000){
cout<<"o"<<left<<setw(4)<<ans[i][j]<<" ";
}
else{
cout<<"x"<<left<<setw(4)<<ans[i][j]<<" ";
}
}
cout<<endl;
}
cout<<endl<<endl; */调试部分
int mina=1e9;
for(int i=0;i<305;i++){
for(int j=0;j<305;j++){
if(ans[i][j]!=-1&&meteor[i][j]>1000){
mina=min(mina,ans[i][j]);
}
}
}
if(mina==1e9){
cout<<"-1";
}else{
cout<<mina;
}
}
by mortal_kiyana @ 2022-07-08 21:36:18
meteor[temp.x][temp.y]=t;
这个也要在前面加一个if判断,判断是否有焦土过还有时间是否是最先的,我开始也是错这个,我改了之后AC了,或者你这个弄5个方向第一个为0,0这样就可以把五个点都判断了
for(int j=0;j<5;++j){
if(sx+tox[j]>=0&&sy+toy[j]>=0&&(ys[sx+tox[j]][sy+toy[j]]==-1||ys[sx+tox[j]][sy+toy[j]]>st)){
ys[sx+tox[j]][sy+toy[j]]=st;
这个就是我的输入判断