#include <iostream>
#include <cstring>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 500;
const int INF = 50000000;
int M;
struct Meteor {
int X, Y;
int Time; //Time_i
Meteor(int X = 0, int Y = 0, int T = 0) :
X(X), Y(Y), Time(T) {}
bool operator < (const Meteor& b) { // 升序排序
return Time < b.Time;
}
} meteor[50000 + 3];
int dir[5][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {0, 0}};
bool used[maxn][maxn];
int field[maxn][maxn]; //标记好每个位置被流星砸(以及扩散到)的时间
int last;
int ans;
void input();
void solve();
bool check(int r, int c, int T);
int BFS(int r, int c, int T);
void input()
{
memset(used, false, sizeof(used));
for (int i = 0; i < maxn; i++) {
for (int j = 0; j < maxn; j++) {
field[i][j] = INF;
}
}
scanf("%d", &M);
for (int i = 0; i < M; i++) {
scanf("%d%d%d", &meteor[i].X, &meteor[i].Y, &meteor[i].Time);
}
sort(meteor, meteor + M); //按照时间升序排序
last = meteor[M - 1].Time; //最后被毁灭的时间
for (int i = 0; i < M; i++) //M个火球
{
for (int j = 0; j < 5; j++) { //5个方向
int x = meteor[i].X + dir[j][0],
y = meteor[i].Y + dir[j][1];
if ( check(x, y, meteor[i].Time) ) {
field[x][y] = meteor[i].Time; //x,y位置和周围扩散位置,破坏的时间
}
}
}
}
bool check(int r, int c, int T)
{
return r >= 0 && c >= 0 && field[r][c] > T;
}
int BFS(int r, int c, int T)
{
used[r][c] = true; //从原点开始
queue<Meteor> que;
Meteor cur;
cur.X = r, cur.Y = c, cur.Time = T;
que.push(cur); //开始的位置，和时间
while (!que.empty())
{
Meteor m = que.front(); que.pop();
for (int i = 0; i < 4; i++) { //遍历4个方向, 因为最后一个方向,是在原地
cur = m;
cur.X = m.X + dir[i][0],
cur.Y = m.Y + dir[i][1]; //周围位置
cur.Time++; //移到下个位置的时间
//如果火球落到该位置的时间>当前人的时间,表示还有机会移动
if (check(cur.X, cur.Y, cur.Time) && !used[cur.X][cur.Y]) {
used[cur.X][cur.Y] = true;
//说明当前位置时间永远不会被炸到
//last是最后被炸到的时间
if (field[cur.X][cur.Y] > last) {
return cur.Time; //则返回当前到达安全的时间
}
que.push(cur); //否则入队列
}
}
}
return -1; //不存在安全位置
}
void solve()
{
input();
if (field[0][0] == 0) { //原点就被毁灭, 反应时间为0
printf("-1
");
}
else {
printf("%d
", BFS(0, 0, 0));
}
}
int main()
{
solve();
return 0;
}
分析:1. 还是经典的BFS问题，主要是要 对被摧毁的位置的时间进行记录(先升序处理)(以及波及到的位置进行时间标志).
2. 人行打算走下一步的时候, 先判断是否时间允许，允许标志为访问过（允许的时候，需要当前位置时间是否已经超过了 最后被毁灭位置的时间，是则返回 到达该安全位置的时间）。不允许则添加到队列中。