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
不要太在意我的奇怪的码风