63分BFS,TLE求助

P2895 [USACO08FEB] Meteor Shower S

就决定是你辣 @ 2022-09-08 17:17:44

rt,是不是状态剪枝出了问题TAT

#include<bits/stdc++.h>
using namespace std;
bool p[305][305];
bool d[305][305];
bool e[305][305];
struct node{
    int t,x,y;
    bool operator<(const node &a)const{return t<a.t;}
}star[50005];
queue<node>q;
int main(){
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&star[i].x,&star[i].y,&star[i].t);
    }
    sort(star+1,star+1+m);
    for(int j=1;j<=m;j++){
        d[star[j].x][star[j].y]=1;
        d[star[j].x+1][star[j].y]=1;
        d[star[j].x-1][star[j].y]=1;
        d[star[j].x][star[j].y+1]=1;
        d[star[j].x][star[j].y-1]=1;
    }
    q.push(node{0,0,0});
    int j=1;
    while(!q.empty()){
        int x=q.front().x;
        int y=q.front().y;
        int t=q.front().t;
        e[x][y]=1;
        q.pop();
        while(t>=star[j].t&&j<=m){
            p[star[j].x][star[j].y]=1;
            p[star[j].x+1][star[j].y]=1;
            if(star[j].x-1>=0)p[star[j].x-1][star[j].y]=1;
            p[star[j].x][star[j].y+1]=1;
            if(star[j].y-1>=0)p[star[j].x][star[j].y-1]=1;
            j++;
        }
        if(y<0||x<0||p[x][y]){
            continue;
        }
        if(!d[x][y]){
            //cout<<x<<" "<<y<<endl; 
            cout<<t<<endl;
            return 0;
        }
        if(!e[x][y+1])q.push(node{t+1,x,y+1});
        if(y>0||!p[x][y-1]||!e[x][y-1])q.push(node{t+1,x,y-1});
        if(!e[x+1][y])q.push(node{t+1,x+1,y});
        if(x>0||!p[x-1][y]||!e[x-1][y])q.push(node{t+1,x-1,y});
    }
    cout<<-1<<endl;
} 

by 燕返 @ 2022-09-17 14:49:49

我觉得你的程序写的有问题的地方

有问题


by 就决定是你辣 @ 2023-02-26 19:39:34

我是傻逼!!!!


|