【题解】POJ 3669 Meteor Shower(BFS)

news/2024/10/30 9:22:55/

POJ 3669 Meteor Shower


https://vjudge.net/problem/POJ-3669

题意

有一场流星雨即将到来,Bessie要找到一个安全的地方。现在已知有M颗流星,并且知道它们抵达的位置和时间,Bessi走一个单位需要一个单位时间,问到达安全位置的最短时间,如果无法到达安全位置就输出-1。
细则:
1、Bessie从起点出发,可以向上下左右四个方向行走。
2、流星会摧毁自己所在点以及该点上下左右的点。
3、在流星刚好到达或者被流星摧毁过的位置都是不可到达的。

Sample Input

4
0 0 2
2 1 2
1 1 2
0 3 5

Sample Output

5

思路:其实就是一个求最短路的问题,只是因为终点无法固定下来用最短时间来替代,所以用BFS从起点在身边搜,搜到安全的位置就停止就好了。


#include<iostream>
#include<cstring>
#include<queue>using namespace std;const int INF = 0x3f3f3f3f;
const int Maxn = 300 + 10;
typedef struct {int x,y,t;	//分别是流星到达的坐标和时间
}node;
node now, next;//当前点以及即将抵达的点
int mp[Maxn][Maxn];
int dir[][2]= {{1,0},{-1,0},{0,1},{0,-1},{0,0}};//多了一个(0,0),因为流星会摧毁所在点int bfs() {if(mp[0][0] == -1)return 0;//如果起点安全就直接返回if(mp[0][0] == 0)return -1;//如果直接被流星砸到,返回-1queue <node> que;now.x = 0;now.y = 0;now.t = 0;//原点que.push(now);while(!que.empty()) {now = que.front();que.pop();for(int i = 0; i < 4; i++) {next.x = now.x + dir[i][0];next.y = now.y + dir[i][1];next.t = now.t + 1;	//一步一秒if(next.x < 0 || next.y < 0)continue;//出界if(mp[next.x][next.y] == -1)//找到安全位置return next.t;if(next.t >= mp[next.x][next.y])//该点已被摧毁continue;mp[next.x][next.y] = next.t;//防止再次走到这个点que.push(next);}}return -1;
}
int main() {memset(mp, -1, sizeof(mp));//mp初始化为-1int m;cin >> m; int xi, yi, ti;for(int i = 0; i < m; i++) {cin >> xi >> yi >> ti;for(int j = 0; j < 5; j++) {	//记录被摧毁时间int nx = xi + dir[j][0];int ny = yi + dir[j][1];if(nx < 0 || nx > 300 || ny < 0 || ny > 300)continue;if(mp[nx][ny] == -1)//未被摧毁直接赋值mp[nx][ny] = ti;else	//被摧毁过记录最早时间mp[nx][ny] = min(mp[nx][ny], ti);}}cout << bfs() << endl;return 0;
}

http://www.ppmy.cn/news/131388.html

相关文章

poj3669

题意&#xff1a;巨大流星雨即将袭来。每个流星会对击中的地方以及周围&#xff08;上下左右四格&#xff09;造成破坏。Bessie开始时位于&#xff08;0, 0&#xff09;位置&#xff0c;并希望逃到一处不会被袭击到的地方&#xff08;在第一象限内&#xff09;。已知每移动一格…

bzoj3669

对于这道题的解法&#xff0c;感觉是部分暴力&#xff0c;枚举带几只A型守护精灵&#xff0c;就可以将这道题转化成求类似于bzoj2594了。 参考题解&#xff1a; http://wenku.baidu.com/view/a611cec4dd3383c4bb4cd2d8.html http://www.cnblogs.com/JoeFan/p/4451249.html 找错…

poj 3669

bfs的题 因为每次都模拟流行砸下来&#xff0c;tle一次&#xff0c;&#xff08;应该标记每个点被砸的时间&#xff09; 因为没有标记走过的点不能再走&#xff0c;tle了一次&#xff0c;&#xff08;之前认为走过的点应该可以再走&#xff0c;其实仔细想的话&#xff0c;走过的…

ORACLE ASM常用命令整理

ASM 命令整理 一. 查看ASM空间使用情况 1. lsdg: 查看磁盘组的信息&#xff0c;和磁盘空间大小 ASMCMD> lsdg State Type Rebal Block AU Total_MB Free_MB Usable_file_MB Offline_disks Voting_files Name MOUNTED EXTERN N 4096 1048576 …

POJ-3669广度优先搜索

这是一道典型的广度优先搜索BFS题目。 首先声明一下&#xff0c;我在这里借鉴了别人的想法&#xff1a;这是原文答案&#xff0c;请点击 题目大意&#xff1a; 流星雨即将攻击地球&#xff0c;当然数目是有限的&#xff0c;共n个&#xff0c;攻击到某个点时将会使该点及其上…

POJ 3669(优先队列BFS)(对地图进行优化)

题目新颖&#xff0c;解法也是比较难想的。 题目&#xff1a; Bessie听说有场史无前例的流星雨即将来临&#xff1b;有谶言&#xff1a;陨星将落&#xff0c;徒留灰烬。为保生机&#xff0c;她誓将找寻安全之所&#xff08;永避星坠之地&#xff09;。目前她正在平面坐标系的…

“3.15”十五个行业大调查:谁在侵害消费者权益?

疫情之后消费复苏&#xff0c;“烟火人间“回归日常。 但是&#xff0c;部分行业的繁华羽翼之下却暗藏斑点&#xff0c;侵害消费者权益的各种乱象丛生&#xff1a; 新餐饮经营异常&#xff0c;食材口感与消费者期望严重不符&#xff1b;厨房小家电价格飘忽不定&#xff0c;参数…

苹果二手报价及图片大全

苹果二手价格一直很多人关注&#xff0c;下面给大家看看最新的二手苹果手机价格。&#xff08;数据来源&#xff1a;换换二手交易平台&#xff09;