这题预处理比较蛋疼,因为可能出现陨石攻击区域重合和同一个格子多个陨石的情况,要先看一下这个位置是否被其他陨石影响,如果已经被影响,就应该取两者时间的较小值,随后更新当前这个陨石的影响范围,注意:如果这个陨石影响的区域中如果存在已经被其他陨石影响的情况,就取两者最小值,否则设置为当前陨石的时间
#include<iostream>
#include<queue>
using namespace std;
#define PII pair<int, int>
#define x first
#define y second
const int M = 310;
int m;
int level[M][M];
int w[M][M], st[M][M];
int dx[] = {0, 0, 1, 0, -1}, dy[] = {0, 1, 0, -1, 0};
int bfs(){
queue<PII> q;
q.push({0, 0});
while(q.size()){
auto h = q.front();
q.pop();
if(st[h.x][h.y] == 0) return level[h.x][h.y];
for(int i = 1; i < 5; i ++){
int a = h.x + dx[i], b = h.y + dy[i];
if(a < 0 || b < 0 || level[a][b]) continue;
if(st[a][b] && level[h.x][h.y] + 1 >= w[a][b]) continue;
level[a][b] = level[h.x][h.y] + 1;
q.push({a, b});
}
}
return -1;
}
int main(){
cin >> m;
while(m --){
int x, y, t;
cin >> x >> y >> t;
for(int i = 0; i < 5; i ++){
int a = x + dx[i], b = y + dy[i];
if(a < 0 || b < 0) continue;
if(st[a][b]) w[a][b] = min(w[a][b], t);
else w[a][b] = t, st[a][b] = 1;
}
}
cout << bfs() << endl;
return 0;
}