爱华网| Time Limit:1000MS | Memory Limit:65536K | |
| Total Submissions:4643 | Accepted: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注意：输入的点的数据范围可能超出题目所给的范围，但是安全区域的范围就是其母所给的范围，分清楚两者的关系就好了。
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;
}
