卷王 @ 2022-04-07 21:33:48
这题的数据范围是300,我就开了301的数组,但是RE了,至少要改成381才能过,这是为什么?蒟蒻表示不懂。。。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
struct node {
int x,y;
};
queue<node>Q;
int ans[310][310],death[310][310];
int work[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
int main()
{
int n;
cin>>n;
memset(death,0x7f,sizeof(death));
memset(ans,-1,sizeof(ans));
for(int i=0;i<n;i++)
{
int x,y,t;
cin>>x>>y>>t;
#define MIN(x,y,t) if(x>=0 && y>=0) death[x][y]=min(death[x][y],t);
MIN(x,y,t);
for(int j=0;j<4;j++)
MIN(x+work[j][0],y+work[j][1],t);
}
Q.push((node){0,0});
ans[0][0]=0;
while(!Q.empty())
{
node u=Q.front();
Q.pop();
int ux=u.x,uy=u.y;
for(int i=0;i<4;i++)
{
int r=ux+work[i][0],s=uy+work[i][1];
if(r<0 || s<0 || ans[r][s]!=-1 || ans[ux][uy]+1
>=death[r][s]) continue;
ans[r][s]=ans[ux][uy]+1;
Q.push((node){r,s});
}
}
int a=1000000;
for(int i=0;i<=305;i++)
for(int j=0;j<=305;j++)
if(ans[i][j]!=-1 && death[i][j]>1000)
a=min(a,ans[i][j]);
if(a!=1000000) cout<<a;
else cout<<"-1";
return 0;
}
by Ginger_he @ 2022-04-07 21:36:46
@holdyhao_Genius 没问题,看题解
by 王君诺 @ 2022-04-07 21:37:53
@holdyhao_Genius
由于流星可能砸到从(0,0)到(300,300)的所有坐标,所以bessie有可能走到300外的点,开数组的时候不能开小了。
by 卷王 @ 2022-04-08 16:59:13
哦,明白了,感谢大佬!
by 262620zzj @ 2022-07-15 23:12:23
@王君诺 那也不对啊,流星的波及范围最大也就是(301,301),为什么要走到380?