洛谷P2895 Meteor Shower S（流星雨）

本文主要是介绍洛谷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

输出 #1

看题目很容易想到用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//找不到输出-1printf("-1\n");return 0;
}

这篇关于洛谷P2895 Meteor Shower S（流星雨）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！