QODGOD @ 2021-01-30 11:54:54
#include<bits/stdc++.h>
using namespace std;
int M;
typedef struct star{//存放流星的坐标和时间
int x;
int y;
int t;
}star;
typedef struct loc{//记录当前人到达的位置
int x;
int y;
}loc;
star S[50005];
int mp[305][305];//记录到达某个位置需要走几步,也就是需要的时间
int vis[305][305];//是否被访问过,或被流星砸到过
int ans;
int move[5][5]={{-1,0},{0,1},{1,0},{0,-1},{0,0}};//移动数组
queue<loc> q;//建立位置队列
bool check(int X,int Y){//check函数用于检查是否永远安全,若永远安全则结束搜索,输出答案
for(int i=0;i<M;i++){//m个流星遍历
for(int j=0;j<5;j++){//流星可以砸到5个方块
if(X==S[i].x+move[i][0]&&Y==S[i].y+move[j][1]){
return false;
}
}
}
//若不会被砸到说明永远安全就记录答案
return true;
}
void bfs(int x,int y){
vis[x][y]=1;
loc k,a,b;
k.x=x;
k.y=y;
q.push(k);
while(!q.empty()){
a=q.front();
q.pop();
for(int i=0;i<M;i++){
if(mp[a.x][a.y]==S[i].t){//到达所需的行动次数与时间相等,所以查找当前时间有无流星坠落并改变地形
int m,n;
m=S[i].x+move[i][0];
n=S[i].y+move[i][1];
for(int j=0;j<5;j++){
if(m>=0&&n>=0)
vis[m][n]=1;//改变地形,被砸到的地方不能被访问
}
}
}
for(int i=0;i<4;i++){
b.x=a.x+move[i][0];
b.y=a.y+move[i][1];
if(check(b.x,b.y)){//若是安全的,结束循环,输出答案
ans=mp[a.x][a.y]+1;
break;
}
if(vis[b.x][b.y]==0&&b.x>=0&&b.y>=0){//如果没有被访问并且在范围内,则计入队列
mp[b.x][b.y]=mp[a.x][a.y]+1;
q.push(b);
vis[b.x][b.y]=1;
}
}
if(check(b.x,b.y)) break;//结束while的循环
}
}
int main(){
cin>>M;
memset(mp,-1,sizeof(mp));//初始化为-1,若不能到达则输出-1
memset(vis,0,sizeof(vis));//未访问则为0,访问后为1
for(int i=0;i<M;i++){
cin>>S[i].x>>S[i].y>>S[i].t;
}
mp[0][0]=0;//起点的初始化
vis[0][0]=1;
bfs(0,0);
cout<<ans;
}