POJ3669(Meteor Shower)(bfs求最短路)

Meteor Shower

Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 12642   Accepted: 3414

Description

Bessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash into earth and destroy anything they hit. Anxious for her safety, she vows to find her way to a safe location (one that is never destroyed by a meteor) . She is currently grazing at the origin in the coordinate plane and wants to move to a new, safer location while avoiding being destroyed by meteors along her way.

The reports say that M meteors (1 ≤ M ≤ 50,000) will strike, with meteor i will striking point (XiYi) (0 ≤ X≤ 300; 0 ≤ Y≤ 300) at time Ti (0 ≤ Ti  ≤ 1,000). Each meteor destroys the point that it strikes and also the four rectilinearly adjacent lattice points.

Bessie leaves the origin at time 0 and can travel in the first quadrant and parallel to the axes at the rate of one distance unit per second to any of the (often 4) adjacent rectilinear points that are not yet destroyed by a meteor. She cannot be located on a point at any time greater than or equal to the time it is destroyed).

Determine the minimum time it takes Bessie to get to a safe place.

Input

* Line 1: A single integer: M
* Lines 2..M+1: Line i+1 contains three space-separated integers: XiYi, and Ti

Output

* Line 1: The minimum time it takes Bessie to get to a safe place or -1 if it is impossible.

Sample Input

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

Sample Output

5

Source

USACO 2008 February Silver

题意:用最短的时间找到最安全的位置。

注意坑:1.当坐标为(0,0)时,上下左右扩展时下标会越界。

2. 每个地点的时间可能重复,取最小的。

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <set>
using namespace std;

const int INF=0x3f3f3f3f;
const double eps=1e-10;
const double PI=acos(-1.0);
#define maxn 310

struct Node
{
    int x,y,t;
};

int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
int vis[maxn][maxn];
int pic[maxn][maxn];
int n;
void bfs()
{
    Node a,b;
    a.x = 0; a.y = 0; a.t = 0;
    queue<Node> sun;
    sun.push(a);
    while(!sun.empty())
    {
        Node temp = sun.front();
        sun.pop();
        for(int i = 0; i < 4; i++)
        {
             b.x = temp.x + dx[i];
             b.y = temp.y + dy[i];
             b.t = temp.t + 1;

             if(b.t < pic[b.x][b.y] && !vis[b.x][b.y]&&b.x>=0&&b.y>=0)
            {
                vis[b.x][b.y] = 1;
                //puts("QAQ");
                if(pic[b.x][b.y] == INF )
                {
                    printf("%d\n", b.t);
                    return;
                }
                //printf("%d %d\n", b.x, b.y);
                sun.push(b);
            }
        }
    }
    printf("-1\n");
}
int main()
{
    while(~scanf("%d", &n))
    {
        memset(pic, INF, sizeof pic);
        memset(vis, 0, sizeof vis);
        int x,y,t;
        for(int i = 0; i < n; i++)
        {
            scanf("%d%d%d", &x,&y,&t);
            pic[x][y] = min(pic[x][y],t);
            for(int j = 0; j < 4; j++)
            {
                int nx = x + dx[j];
                int ny = y + dy[j];
                if(nx >= 0 && ny >= 0)
                pic[nx][ny] = min(pic[nx][ny],t);
            }
        }
        vis[0][0] = 1;
        bfs();
    }
    return 0;
}
时间: 12-20

POJ3669(Meteor Shower)(bfs求最短路)的相关文章

poj3669 Meteor Shower(BFS)

题目链接:poj3669 Meteor Shower 我只想说这题WA了后去看讨论才发现的坑点,除了要注意原点外,流星范围题目给的是[0,300],到302的位置就绝对安全了... 1 #include<cstdio> 2 #include<cmath> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 #define CLR(a,b) memset((a),(b),siz

UVa 816 (BFS求最短路)

/*816 - Abbott's Revenge ---代码完全参考刘汝佳算法入门经典 ---strchr() 用来查找某字符在字符串中首次出现的位置,其原型为:char * strchr (const char *str, int c) ---BFS求最短路 --*/ #define _CRT_SECURE_NO_DEPRECATE #include<iostream> #include<string.h> #include<queue> #include<al

POJ 2251 Dungeon Master --- 三维BFS(用BFS求最短路)

POJ 2251 题目大意: 给出一三维空间的地牢,要求求出由字符'S'到字符'E'的最短路径,移动方向可以是上,下,左,右,前,后,六个方向,每移动一次就耗费一分钟,要求输出最快的走出时间.不同L层的地图,相同RC坐标处是相连通的.(.可走,#为墙) 解题思路:从起点开始分别往6个方向进行BFS(即入队),并记录步数,直至队为空.若一直找不到,则困住. /* POJ 2251 Dungeon Master --- 三维BFS(用BFS求最短路) */ #include <cstdio> #i

bfs求最短路的几道例题

题目来自于记蒜客数据结构课,类型差不多,都是用bfs求最短路(注意是不加权的最短路,加权的情况后面的文章会讲). 代码如下: 1 //记蒜客习题 2 //bfs求某点到其他各点的最短距离 3 #include <iostream> 4 #include <cstring> 5 #include <queue> 6 using namespace std; 7 8 class Graph{ 9 private: 10 int n; 11 bool *visited; 12

UVA 816 -- Abbott&#39;s Revenge(BFS求最短路)

 UVA 816 -- Abbott's Revenge(BFS求最短路) 有一个 9 * 9 的交叉点的迷宫. 输入起点, 离开起点时的朝向和终点, 求最短路(多解时任意一个输出即可).进入一个交叉点的方向(用NEWS表示不同方向)不同时, 允许出去的方向也不相同. 例如:1 2 WLF NR ER * 表示如果 进去时朝W(左), 可以 左转(L)或直行(F), 如果 朝N只能右转(R) 如果朝E也只能右转.* 表示这个点的描述结束啦! 输入有: 起点的坐标, 朝向, 终点的坐标.然后是各个

POJ3669 Meteor Shower 【BFS】

Meteor Shower Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 9163   Accepted: 2594 Description Bessie hears that an extraordinary meteor shower is coming; reports say that these meteors will crash into earth and destroy anything they hi

[codeforces-543B]bfs求最短路

题意:给一个边长为1的无向图,求删去最多的边使得从a到b距离<=f,从c到d距离<=g,a,b,c,d,f,g都是给定的,求最多删去的边数. 思路:反过来思考,用最少的边构造两条从a到b,从c到d的路径,使得它们满足题目中的条件.于是可以把这两条路径的相对位置分为两种情况,不相交和相交,对于不相交的情况答案就是两组距离之和,对于相交的情况,两条路径肯定共享一段连续路径,对于共享多段的情况可以把中间没共享的取较小值变成共享,得到的距离和不会更大,因此最优情况一定是一段连续的路径.于是可以枚举共享

UVa439 Knight Moves (BFS求最短路)

链接:http://acm.hust.edu.cn/vjudge/problem/19436分析:BFS跑一次最短路,状态转移有8个. 1 #include <cstdio> 2 #include <queue> 3 #include <cstring> 4 using namespace std; 5 6 struct Point { 7 char r, c; 8 Point(char r = ' ', char c = ' '): r(r), c(c) {}; 9

POJ - 3669 Meteor Shower(bfs)

题意:某人在时刻0从原点出发,在第一象限范围内移动.已知每个炸弹爆炸的地点和时刻,炸弹爆炸可毁坏该点和它上下左右的点.不能经过已毁坏的点,也不能在某点毁坏的时候位于该点.不会被炸弹毁坏的地方是安全之处,问某人到达安全之处的最短时间. 分析:bfs即可.注意:1.某点多次爆炸或受爆炸点影响而毁坏,取最早时间为该点的毁坏时间.2.bfs走过的点不能再走,注意标记. #pragma comment(linker, "/STACK:102400000, 102400000") #include