新手42求调

P2895 [USACO08FEB] Meteor Shower S

kendas @ 2024-12-19 14:59:37

不知道为什么会有RE

有两个TLE(完全接受<-)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int m;
const int N = 310;
vector<pair<PII,int>>q;
int g[N][N];
int dx[]{1,0,-1,0},dy[]{0,-1,0,1};
pair<PII,int> f[N*N];
int hh, tt = -1;
int bfs()
{
    //记录当前坐标和当前时间
    f[++ tt] = {{1,1},0};
    while(hh <= tt)
    {
        auto t = f[hh ++];
        //不在预测的-1位置,是安全点
        if(g[t.first.first][t.first.second] == 0)
        {
            // cout << t.first.first << ' ' << t.first.second << endl;
            return t.second;
        }
        //先砸下陨石看看
        for(int i = 0; i < q.size(); i ++)
        {
            if(q[i].second <= t.second)
            {
                g[q[i].first.first][q[i].first.second] = 1;
                for(int j = 0; j < 4; j ++)
                {
                    int tx = q[i].first.first + dx[j],ty = q[i].first.second + dy[j];
                    if(tx >= 1 && ty >= 1)
                    g[tx][ty] = 1;
                }
            }
        }
        //发现自己被砸死
        if(g[t.first.first][t.first.second] == 1)continue;
        //没被砸死就进行瞎走
        for(int i = 0; i < 4; i ++)
        {
            int tx = t.first.first + dx[i], ty = t.first.second + dy[i];
            if(g[tx][ty] != 1 && tx >= 1 && ty >= 1)
            {
                f[++ tt] = {{tx,ty},t.second+1};
            }
        }

    }
    return -1;
}

int main()
{
    cin>>m;
    for(int i = 1; i <= m; i ++)
    {
        int x,y,t;
        scanf("%d%d%d",&x,&y,&t);
        //以(1,1)为棋盘初始点
        q.push_back({{x+1,y+1},t});
    }
    //先预测哪些点是安全点,将会被陨石砸的点标记为-1,这样之后bfs就可以知道自己是不是在安全点
    for(int i = 0; i < q.size(); i ++)
    {
        g[q[i].first.first][q[i].first.second] = -1;
        for(int j = 0; j < 4; j ++)
        {
            int tx = q[i].first.first + dx[j], ty = q[i].first.second + dy[j];
            if(tx >= 1 && ty >= 1)
                g[tx][ty] = -1;
        }
    }
    cout << bfs();

}

by kendas @ 2024-12-24 15:11:22

@kendas

解决了,st数组应该提前标记,而不是不用或者再bfs尾部标记为true,会导致大量重复入队


|