贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。
如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。
根据预报，一共有?M?颗流星 (1≤M≤50,000)?会坠落在农场上，其中第?i?颗流星会在时刻?Ti?（0≤Ti?≤1000）砸在坐标为(Xi?,Yi?)(0≤Xi?≤300，0≤Yi?≤300)?的格子里。流星的力量会将它所在的格子，以及周围?4?个相邻的格子都化为焦土，当然贝茜也无法再在这些格子上行走。
贝茜在时刻?0?开始行动，她只能在第一象限中，平行于坐标轴行动，每?1?个时刻中，她能移动到相邻的（一般是?4?个）格子中的任意一个，当然目标格子要没有被烧焦才行。如果一个格子在时刻?t?被流星撞击或烧焦，那么贝茜只能在?t?之前的时刻在这个格子里出现。 贝茜一开始在?(0,0)。
请你计算一下，贝茜最少需要多少时间才能到达一个安全的格子。如果不可能到达输出??1。
共 M+1?行，第?1?行输入一个整数?M，接下来的?M?行每行输入三个整数分别为 Xi?,Yi?,Ti?。
贝茜到达安全地点所需的最短时间，如果不可能，则为??1。
输入 #1
4 0 0 2 2 1 2 1 1 2 0 3 5
输出 #1
5
看题目很容易想到用bfs，然而与其他题目不同的是，这里某些点不是一来就不可以走的，而是要根据流星落下的时间来判断，在流星落下之前可以走，落下之后就不能走了。
解题思路
我们可以使用三个二维数组分别储存
1.每一个点流星最早落下的时间（注意：一个点可能有多个流星落下，只需要取最早落下的时间就可以了）
2.这个点是否已经走过（避免多次到达同一个点）
3.这个点是否有流星落下（用来寻找安全点）
对于一个点是否能够到达只需要比较
这题主要有3个容易出错的点
1.对于初始点要进行特判（即初始点就是安全地点）
2.走出农场就会绝对安全（即坐标大于300）
3.走不到安全地点输出-1
AC代码
#include<stdio.h>
//book数组用来标记这个点是否已经走过，book2标记这个点是否会有流星落下，book1标记这个点流星落下的时间
int book[410][410], book1[410][410], book2[410][410], nest[4][2] = { {0,1},{1,0},{-1,0},{0,-1} };//nest方向数组
struct nb {
int x;//横坐标
int y;//纵坐标
int s;//到达这个点的时间
} a[90020];//建立列队
int main()
{
int n, i, j;
scanf("%d", &n);
for (i = 0; i <= 405; i++)//初始化所有点流星落下时间为无穷大
{
for (j = 0; j <= 405; j++)
{
book1[i][j] = 1e9;
}
}
for (i = 1; i <= n; i++)
{
int g, k, h;
scanf("%d %d %d", &g,&k,&h);//g,h,h分别代表横坐标，纵坐标，流星落下的时间
if (book1[g][k] > h)//取最小时间
book1[g][k] = h;
book2[g][k] = 1;//标记这个点会有流星落下
for (j = 0; j <= 3; j++)//列举3个方向
{
int tx = g + nest[j][0];
int ty = k + nest[j][1];
if (tx < 0 || tx>400 || ty < 0 || ty>400)//注意（这里如果只写300，会出错因为会有走出农场的情况）
continue;
if (book1[tx][ty] > h)//对周围4个点进行判断
book1[tx][ty] = h;
book2[tx][ty] = 1;
}
}
if (book2[0][0] == 0)//特判初始点是否安全
{
printf("0\n");
return 0;
}
//列队
int hard = 1, tail = 1;
a[tail].x = 0;//初始横坐标
a[tail].y = 0;//初始纵坐标
a[tail].s = 0;//初始步数
book[0][0] = 1;//标记初始点已经走过
tail++;
int flag = 0;//flag等于1时代表已经找到了
while (hard < tail)
{
for (i = 0; i <= 3; i++)
{
int tx = a[hard].x + nest[i][0];
int ty = a[hard].y + nest[i][1];
if (tx < 0 || tx>400 || ty < 0 || ty>400)
continue;
if (a[hard].s + 1 >= book1[tx][ty])//如果走到这个点的时间大于这个点流星落下的时间这个点就不能走
continue;
if (book[tx][ty] == 0)//这个点之前没被走过才走
{
a[tail].x = tx;
a[tail].y = ty;
a[tail].s = a[hard].s + 1;
book[tx][ty] = 1;
tail++;
}
if (book2[tx][ty] == 0)//如果找到安全地点
{
flag = 1;
break;
}
}
if (flag == 1)
{
break;
}
hard++;
}
if (flag == 1)//找到输出最小时间
printf("%d\n", a[tail - 1].s);
else//找不到输出-1
printf("-1\n");
return 0;
}