大佬们救救孩子吧,注释打好了,最后两个点RE

P2895 [USACO08FEB] Meteor Shower S

dysprositos @ 2023-03-18 21:41:22

自己已经试过了,如果二维数组开300300大概会re最后5个,但是我开到2000020000只会re最后两个。 球球大佬救救+

#include<iostream>
#include<queue>
#include<climits>
#include<algorithm>

using namespace std;
const int N=20000,M=1e5;
int g[N][N],dx[5]={1,-1,0,0,0},dy[5]={0,0,1,-1,0};
int m,t1;
queue<pair<int,int>> q;

class meteors
{
    public:
        int t,x,y;
}me[N];

bool cmp(meteors a,meteors b)
{
    if(a.t<=b.t)return true;
    else return false;
}

void destory(int x,int y)//流星摧毁的地方
{
    for(int i=0;i<5;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a>=0&&a<=302&&b>=0&&b<=302)
        g[a][b]=-1;
    }
}

void bfs()
{
    int k=q.size();
    t1++;

    while(k--)
    {
        auto t=q.front();
        q.pop();

        if(g[t.first][t.second]>=0)//若该起点没被砸,就再存一次,因为上面遍历时把他删了
        {
            q.push(t);
        }

        for(int i=0;i<4;i++)
        {
            int a=t.first+dx[i],b=t.second+dy[i];
            if(a>=0&&a<=302&&b>=0&&b<=302&&!g[a][b])
            {
                g[a][b]=t1;
                q.push({a,b});
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie();

    q.push({0,0});

    cin >> m;
    int X,Y;
    for(int i=0;i<m;i++)//记录所有流星坐标、时间
    {
        cin >> me[i].x >> me[i].y >> me[i].t;
    }

    sort(me,me+m,cmp);

    for(int i=0;i<m;i++)//对过程的模拟,如第一颗两秒砸地,
    //先dfs零到一秒,零到二秒时先让流星砸了再dfs零到二秒
    {
        while(t1<me[i].t-1)
        {
            bfs();
        }
        destory(me[i].x,me[i].y);
    }

    bfs();//最后一颗流星砸了后没有进行搜索,再搜一次

    //没地儿就-1
    if(q.size()==0)
    {
        cout << "-1";
        return 0;
    }
    //找最小
    int x=INT_MAX;
    int cnt=q.size();
    for(int i=0;i<cnt;i++)
    {
        x=min(x,g[q.front().first][q.front().second]);
        q.pop();
    }

    cout << x;
}

by dysprositos @ 2023-03-18 22:01:29

呜呜呜,对不起,你们骂我吧。我这道题写太久写昏了。最后我的流星结构数组用的N,改回M就好了 二维数组看来不用开这么大,稍微过300就行了,大家别忘了流星的范围时1e5


|