poj3669MeteorShower(BFS)_crystal poj 1979 bfs

MeteorShower
Time Limit:1000MSMemory Limit:65536K
Total Submissions:4643Accepted:1370

Description

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

The reports saythatMmeteors (1≤M≤ 50,000) will strike,with meteoriwillstriking point(Xi,Yi) (0≤Xi≤ 300; 0≤Yi≤ 300) attimeTi(0≤Ti ≤ 1,000).Each meteor destroys the point that it strikes and also the fourrectilinearly adjacent lattice points.

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

Determine the minimum time it takes Bessie to get to a safeplace.

Input

* Line 1: A single integer:M
* Lines 2..M+1: Linei+1 containsthree space-separatedintegers:Xi,Yi,andTi

Output

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

Sample Input

40 0 22 1 21 1 20 3 5

Sample Output

5

Source

USACO 2008February Silver
注意:输入的点的数据范围可能超出题目所给的范围,但是安全区域的范围就是其母所给的范围,分清楚两者的关系就好了。
poj3669MeteorShower(BFS)_crystal poj 1979 bfs
code:

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define INF 100000000

#define le 302

#define lne 50005

const int elem = 301;

typedef struct{

int r,c,dis;

}re;

re q[le * le];

int der[4][2] ={{-1,0},{1,0},{0,-1},{0,1}};

int vis[le][le];

int map[le][le];

int m;

void init(){

int i,j;

for(i = 0 ; i < le ; i++)

for(j = 0 ; j < le ; j++)

map[i][j] = INF;

}

void input(){

int i,u,v,w;

init();

for(i = 0 ; i < m ; i++){

scanf("%d%d%d",&u,&v,&w);

if(w < map[u][v]) map[u][v] =w;

if(u > 0){

if(map[u-1][v] > w) map[u-1][v] =w;

}

if(map[u+1][v] > w) map[u+1][v] =w;

if(v > 0){

if(map[u][v-1] > w) map[u][v-1] =w;

}

if(map[u][v+1] > w) map[u][v+1] =w;

}

}

int BFS(){

int front = 0 , rear = 1 , i;

re tem , g;

if(map[0][0] == INF) return 0;

if(map[0][0] == 0) return -1;

memset(vis , 0 , sizeof(vis));

tem.r = 0; tem.c = 0; tem.dis = 0;

q[front] = tem;

vis[0][0] = 0;

while(front != rear){

tem = q[front++];

if(front == lne) front = 0;

for(i = 0 ; i < 4 ; i++){

g.r = tem.r + der[i][0];

g.c = tem.c + der[i][1];

g.dis = tem.dis + 1;

if(g.r >= 0&& g.r <= elem&& g.c >= 0&& g.c <=elem)

if(!vis[g.r][g.c] &&map[g.r][g.c] > g.dis){

if(map[g.r][g.c] == INF){

return g.dis;

}

vis[g.r][g.c] = 1;

q[rear++] = g;

if(rear == lne) rear = 0;

}

}

}

return -1;

}

void deal(){

int ans = BFS();

printf("%dn",ans);

}

int main(void){

while(scanf("%d",&m) == 1){

input();

deal();

}

return 0;

}


  

爱华网本文地址 » http://www.413yy.cn/a/25101015/242036.html

更多阅读

spfa判断负环(转载)_crystal spfa求负环

判断给定的有向图中是否存在负环。利用 spfa算法判断负环有两种方法:1)spfa 的 dfs形式,判断条件是存在一点在一条路径上出现多次。2)spfa 的 bfs形式,判断条件是存在一点入队次数大于总顶点数。代码如下:法 1 (spfa的 dfs形式):#incl

回顾 1979年电影《小花》演员表、截图介绍与插曲 我的1979小说

根据长篇小说《桐柏英雄》改编的同名电视剧正在央视八套播出,不由联想到北京电影制片厂1979年摄制的的电影《小花》,同样取材于该小说,编剧:前涉,导演:张铮,副导演:黄健中,作曲:王酩。曾于1980年获得第3届电影百花奖最佳故事片、最佳女演员(陈

中华人民共和国刑事诉讼法1979年版 中华共和国刑事诉讼法

中华人民共和国刑事诉讼法(1979年版)(1979年7月1日第五届全国人民代表大会第二次会议通过 1979年7月7日全国人民代表大会常务委员会委员长令第六号公布 自1980年1月1日起施行)时效性:已被修正  失效日期:19970101第一编 总 则第一章 指导思想、任务和

彩色故事片:瞧这一家子(1979).rmvb

瞧这一家子 (1979) (WHAT A FAMILY)导 演:王好为编 剧:林力上 映:1979年地 区:中国大陆颜 色:彩色类 型:剧情片演员表: 陈强 .... 老胡

声明:《poj3669MeteorShower(BFS)_crystal poj 1979 bfs》为网友仰望分享!如侵犯到您的合法权益请联系我们删除