7分 13,14RE 其余WA 求助 只过了第三个测试点和样例

P2895 [USACO08FEB] Meteor Shower S

Francais_Drake @ 2021-09-11 16:51:44

#include <bits/stdc++.h>
using namespace std;
#define rep(i,l,r,step) for(int i=(l);i<(r);i+=step) 
#define per(i,l,r,step) for(int i=(r);i>(l);i-=step)

int m,t[50010],T,d;
int _time,_x,_y,x,y;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
struct meteor{
    int time,x,y;
}met[310];
bool cmp(struct meteor a,struct meteor b){
    return a.time<b.time;
}
bool mp[2][310][310];
bool valid(int X,int Y,int c){
    return X>=0&&X<=300&&Y>=0&&Y<=300&&mp[c][X][Y]==false;//标记陨石掉落&bessie行走(不走环) 
}
int main(){
    scanf("%d",&m);
    rep(i,0,m,1){
        scanf("%d%d%d",&_x,&_y,&_time);
        met[i].time=_time,met[i].x=_x,met[i].y=_y;
        mp[1][_x][_y]=true;
        rep(j,0,4,1){
            _x+=dx[j];
            _y+=dy[j];
            if(valid(_x,_y,1)) mp[1][_x][_y]=true;
            _x-=dx[j];
            _y-=dy[j];
        }
    }
    _time=-1;
    sort(met,met+m,cmp);//按时间从小到大排序 
    queue<pair<pair<int,int>,int> > q;
    q.push(make_pair(make_pair(0,0),0));
    mp[0][0][0]=true;
    while(q.size()){
        x=q.front().first.first;
        y=q.front().first.second;
        T=q.front().second;
        q.pop();
        if(mp[1][x][y]==false){//bessie runs to safe place
            _time=T;
            break;
        }
        while(T==met[d].time){//meteor fells
            rep(i,0,4,1){
                _x=met[d].x;
                _y=met[d].y;
                met[d].x+=dx[i];
                met[d].y+=dy[i];
                if(valid(met[d].x,met[d].y,0)) mp[0][met[d].x][met[d].y]=true;
                met[d].x=_x;
                met[d].y=_y;
            }
            d++;
        }
        rep(i,0,4,1){//Bessie walk
            _x=x;
            _y=y;
            x+=dx[i];
            y+=dy[i];
            if(valid(x,y,0)){
                mp[0][x][y]=true;
                q.push(make_pair(make_pair(x,y),T+1));
            }
            x=_x;
            y=_y;
        }   
    }
    printf("%d\n",_time);
}

by Francais_Drake @ 2021-09-11 16:52:25

不要太在意我的奇怪的码风


|