# 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

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;
}```

## 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

## 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