Meteor Shower（BFS）

B - Meteor Shower

Crawling in process... Crawling failed Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%I64d & %I64u

Submit Status Practice POJ 3669

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 (X_i, Y_i) (0 ≤ X_i ≤ 300; 0 ≤ Y_i ≤ 300) at time T_i (0 ≤ T_i  ≤ 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: X_i, Y_i, and T_i

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

   题意：

   有M颗流星坠落，（Xi,Yi）表示坠落的位置 ，Ti表示坠落的时间，坠落的同时，上下左右四个地方也同样会受到攻击。输出在最小时间，在这个时间内能走到安全的地方，如果不能逃走，则输出-1.

   思路：

   先初始化把所有的点都设为无穷大，然后通过输入M次坐标（Xi,Yi）来改变更新这个点及周围四个点的最小时间。最后从（0,0）点开始进行广搜，从上下左右位置搜（（0,0）点只有上与右），如果找到这个点到（0,0）的距离小于这个格子的最短距离时间，则判断这个点是不是无穷大（即是不是安全地），如果不是则放入队列中以备下一次搜索该点的周围点时使用，如果这个点是无穷大，说明是安全地，这时候输出这个点到（0,0）点的时间即为最小时间。

    AC：

#include<stdio.h>
#include<string.h>
#define BOR 300+5    //最大宽度
#define INT 10000000 //用来表示无穷大 
typedef struct       //模拟队列
{
	int x;       //x坐标
	int y;       //y坐标
	int s;       //距离
}queen;

int   map[BOR][BOR];   //表示整个图
queen q[BOR*BOR];      
int   vis[BOR][BOR];   //记录有无走过该地方
int   dis[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; //坐标位置的上下左右

int bfs(int a,int b)
{
	queen from,to;
	int   f=0,t=1,i;
	from.x=0;from.y=0;from.s=0;
	q[0]=from;
	memset(vis,0,sizeof(vis));
	if(map[0][0]==INT) return 0;  
 //如果本身地方通过一开始初始化后还是无穷数，说明该地方安全
	if(map[0][0]==0)   return -1;
 //如果该地方在0秒是就被轰炸，说明逃不了了
	while(f!=t)  
	{
	   from=q[f++];
	   if(f==BOR) f=0;  //也许走到最边边位置也逃不了
	   	for(i=0;i<4;i++)  //循环四次，表示走该位置的上下左右4个地方
	   	{
	   		to.x=from.x+dis[i][0];
	   		to.y=from.y+dis[i][1];
	   		to.s=from.s+1;      //记录深度，当换下一个深度的时候才+1，不是这个每次循环都+1
	   		if(to.x>=0&&to.y>=0&&to.x<=BOR&&to.y<=BOR&&vis[to.x][to.y]==0&&map[to.x][to.y]>to.s)
	   		{      //如果在范围内，且还没访问过，且这个距离小于初始化后此时的大小
	   			if(map[to.x][to.y]==INT)  return to.s;  
                               //如果这个地方是无穷大，则说明这个地方安全，返回这个时候的距离最短长度，即最短时间
	   			vis[to.x][to.y]=1;          //如果不满足上面条件，则标记这个点为已放访问点
	   			q[t++]=to;          //放入模拟队列中，下一次判断该点周围的点
	   			if(t==BOR) t=0; //也许走到最边边位置也逃不了
	   		}
	   	}
	}
	return -1;    //如果循环上面的步骤的无法返回一个最短时间，则说明逃不了了，返回-1
} 

int main()
{
	int N,i,j;
	int X,Y,T;
	scanf("%d",&N);
	
	for(i=0;i<BOR;i++)   //每个区域位置都未无穷大，假设全都为安全 
	  for(j=0;j<BOR;j++)
	    map[i][j]=INT;
	
	for(i=0;i<N;i++)   //周围点及中心点为所给坐标时间的最小值
	{                  //对输入坐标点及坐标周围点初始化
		scanf("%d%d%d",&X,&Y,&T);
		if(map[X][Y]>T)   map[X][Y]=T;
		if(map[X+1][Y]>T) map[X+1][Y]=T;
		if(X>0&&map[X-1][Y]>T)  map[X-1][Y]=T;
		if(Y>0&&map[X][Y-1]>T)  map[X][Y-1]=T;
		if(map[X][Y+1]>T)  map[X][Y+1]=T;
	}
	printf("%d\n",bfs(0,0));  //输出最短时间
	return 0;
}

  STL的queue写的AC代码：

   

#include<cstdio>
#include<queue>
#include<string.h>
#define BOR 300+5
#define INT 1000000
using namespace std;
struct pos
{
	int x;
	int y;
	int s;
};

int map[BOR][BOR];
int vis[BOR][BOR];
int dis[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
queue<pos> q;

int bfs(int a,int b)
{
	int t;
	pos from,to;
	memset(vis,0,sizeof(vis));
	from.x=0,from.y=0,from.s=0;
	q.push(from);
	if(map[0][0]==INT) return 0;
	if(map[0][0]==0)   return -1;
	while(!q.empty())
	{
		from=q.front();
		for(t=0;t<4;t++)
		{
			to.x=from.x+dis[t][0];
			to.y=from.y+dis[t][1];
			to.s=from.s+1;
			if(to.x>=0&to.y>=0&&to.x<=BOR&&to.y<=BOR&&map[to.x][to.y]>to.s&&vis[to.x][to.y]==0)
			  {
			  	if(map[to.x][to.y]==INT) return to.s;
			  	vis[to.x][to.y]=1;
			  	q.push(to);
			  }
		}
		q.pop();
	}
	return -1;
}

int main()
{
	int N,i,j;
	int x,y,time;
	scanf("%d",&N);
	 
	 for(i=0;i<BOR;i++)
	  for(j=0;j<BOR;j++)
	  map[i][j]=INT;
	  
	for(i=0;i<N;i++)
     {
     	scanf("%d%d%d",&x,&y,&time);
     	if(map[x][y]>time)         map[x][y]=time;
     	if(map[x+1][y]>time)       map[x+1][y]=time;
     	if(map[x][y+1]>time)       map[x][y+1]=time;
     	if(x>0&&map[x-1][y]>time)  map[x-1][y]=time;
     	if(y>0&&map[x][y-1]>time)  map[x][y-1]=time;
     }
   printf("%d\n",bfs(0,0));
}

 

   总结：

   对广搜也有了进一步的了解认识了，一边光想怎么做还是不行，还是需要找资料找下模板看看如何实现广搜才行。很多东西也许看是看懂了，但是一动手写就会出现一堆错误，第一次做出来还是很不踏实，所以一下子Delete所有代码重新写一遍。果然，写了半小时多才写了出来，但是写出来还是一堆错误，而且我不是用STL的queue写的，所以还需要再写一遍来加深加深印象。（第二次修改已经把queue的版本写出来了）