题目描述
贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。
如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。
根据预报，一共有 \(M\) 颗流星 \((1\leq M\leq 50,000)\) 会坠落在农场上，其中第 \(i\) 颗流星会在时刻 \(T_i\)（\(0 \leq T _ i \leq 1000\)）砸在坐标为 \((X_i,Y_i)(0\leq X_i\leq 300\)，\(0\leq Y_i\leq 300)\) 的格子里。流星的力量会将它所在的格子，以及周围 \(4\) 个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。
贝茜在时刻 \(0\) 开始行动，她只能在第一象限中，平行于坐标轴行动，每 \(1\) 个时刻中，她能移动到相邻的（一般是 \(4\) 个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻 \(t\) 被流星撞击或烧焦，那么贝茜只能在 \(t\) 之前的时刻在这个格子里出现。 贝茜一开始在 \((0,0)\)。
请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出 \(−1\)。
输入格式
共 \(M+1\) 行，第 \(1\) 行输入一个整数 \(M\)，接下来的 \(M\) 行每行输入三个整数分别为 \(X_i, Y_i, T_i\)。
输出格式
贝茜到达安全地点所需的最短时间，如果不可能，则为 \(-1\)。
样例 #1
样例输入 #1
4
0 0 2
2 1 2
1 1 2
0 3 5
样例输出 #1
5
解题思路
- 本题求能够到达安全地方所使用的最短时间，安全地方指永远都不会有陨石落下来的地方。要求最短时间，所以考虑用bfs做，用队列存储当前到达的坐标的信息。
- 题目需要特殊处理的地方在于：
1）某一点不安全的时间取决于它自己以及上下左右四个点有陨石落下的最小值（除0之外），因此该点是否能经过，取决于最早到达该点时的时间是否小于最早陨石降落的时间；
2）题中没有限定只能在坐标300以内走，因此判断的时候要开大一点，如305，才能考虑到可以在外圈走的情况；
3）最后需要做特判，如果第0秒坐标原点就有陨石了，那么就game over了。
#include <stdio.h>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int t[310][310], t1[310][310], t_arr[310][310];
bool flag[310][310];
//上下左右四个方向
int dx[4] = {0 , 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
queue<pair<int, int>> q;
int main(){
int m, x, y;
//初始化陨石到达时间
for(int i = 0; i <= 305; i++){
for(int j = 0; j <= 305; j++) t[i][j] = 1005;
}
cin >> m;
for(int i = 1; i <= m; i++){
cin >> x >> y;
cin >> t[x][y];
}
//求当前位置陨石最早到达的时间，如果是安全地方，则t1为1005
for(int i = 0; i <= 305; i++){
for(int j = 0; j <= 305; j++){
t1[i][j] = min(t[i][j], t[i+1][j]);
t1[i][j] = min(t1[i][j], t[i][j+1]);
if(j-1 >= 0) t1[i][j] = min(t1[i][j], t[i][j-1]);
if(i-1 >= 0) t1[i][j] = min(t1[i][j], t[i-1][j]);
}
}
//特判
if(t1[0][0] == 0){
cout << 0 << endl;
return 0;
}
//bfs
q.push(make_pair(0,0));
t_arr[0][0] = 0;
flag[0][0] = 1;
while(!q.empty()){
pair<int, int> p1;
p1 = q.front();
int x = p1.first, y = p1.second;
q.pop();
//如果该坐标是安全的，则输出当前坐标的到达时间
if(t1[x][y] == 1005){
cout << t_arr[x][y] << endl;
return 0;
}
//超出范围，不入队，注意大于305
else if(x < 0 || y < 0 || x > 305 || y > 305 || t_arr[x][y] >= t1[x][y]) {
continue;
}
//向四个方向扩散,入队
for(int i = 0; i < 4; i++){
if(!flag[x+dx[i]][y+dy[i]]){
q.push(make_pair(x+dx[i], y+dy[i]));
flag[x+dx[i]][y+dy[i]] = 1;
t_arr[x+dx[i]][y+dy[i]] = t_arr[x][y] + 1;
}
}
}
cout << -1 << endl;
return 0;
}