洛谷P2895 Meteor Shower S（流星雨）

题目描述

贝茜听说一场特别的流星雨即将到来：这些流星会撞向地球，并摧毁它们所撞击的任何东西。她为自己的安全感到焦虑，发誓要找到一个安全的地方（一个永远不会被流星摧毁的地方）。

如果将牧场放入一个直角坐标系中，贝茜现在的位置是原点，并且，贝茜不能踏上一块被流星砸过的土地。

根据预报，一共有?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;
}