这题的数据范围是不是有问题?

P2895 [USACO08FEB] Meteor Shower S

卷王 @ 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?


|