poj3669 Meteor Shower(bfs预处理)

题目链接：http://poj.org/problem?id=3669

题目大意：

主角贝西听说来了一场流星雨，当然这场流星雨带着破坏性，每颗流星落下会炸毁周边四个地方和被砸地方的中心，即上下左右中五个坐标，主角最开始位于原点，流星按照时间砸下来，

主角需要做的是在流星雨砸不到他的时间内尽可能的跑到安全地点，如不能则返回-1；

题解思路：

这道题依旧是迷宫问题，但不好处理在如何处理这个时间的问题，即流星是按顺序砸下的并且主角每移动一个点就会增加一个单位的时间，所以说在处理这个问题之前采用预处理题目条件的策略，在进行搜索，效果可能更好一些；

需要注意的几个点：

预处理的方式：

 1 memset(a,INF,sizeof(a));//预处理
 2     for(int i=0;i<m;i++)//预处理
 3     {
 4         cin>>dx>>dy>>dt;
 5         a[dx][dy]=min(a[dx][dy],dt);//找最早被破坏的时间就是为了和主角到达的时间进行一个比较，看看当前主角有没有生命危险
 6         for(int j=0;j<4;j++)
 7         {
 8             int nx,ny;
 9             nx=dx+dir[j][0];
10             ny=dy+dir[j][1];
11             if(check(nx,ny))
12             {
13                 a[nx][ny]=min(a[nx][ny],dt);
14             }
15         }
16     }

和如何理解

    if(next.t+1<a[next.x][next.y])//到达下一个地点的时间比被炸毁的时间早，就说明暂无生命危险

当然这段代码我还是写的比较浅显易懂

AC代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 #include<queue>
 5 #include<cmath>
 6 using namespace std;
 7 const int num=1000;
 8 const int INF=0x3f3f3f3f;
 9 int m;
10 bool vis[num][num];
11 int a[num][num];//每个点被破坏的最早时间
12 bool check(int x, int y){
13     if(x < 0 || y < 0 || x >= num || y >= num) 
14     return false;
15     return true;
16 }
17 int dir[4][2]=
18 {
19     {-1,0},
20     {0,-1},
21     {1,0},
22     {0,1},
23 };
24 struct node
25 {
26     int x;
27     int y;
28     int t;
29 };
30 int bfs()
31 {
32     if(a[0][0]==0)//上来就跑不了，则已死
33     return -1;
34     queue<node>q;
35     vis[0][0]=true;
36     node start,next;
37     start.x=0;
38     start.y=0;
39     start.t=0;
40     q.push(start);
41     while(!q.empty())
42     {
43         start=q.front();
44         q.pop();
45         if(a[start.x][start.y]==INF)//安全
46         return start.t;
47         for(int i=0;i<4;i++)
48         {
49             next.x=start.x+dir[i][0];
50             next.y=start.y+dir[i][1];
51             next.t=start.t;
52             if(check(next.x,next.y)&&!vis[next.x][next.y])
53             {
54                 if(next.t+1<a[next.x][next.y])//到达下一个地点的时间比被炸毁的时间早，就说明暂无生命危险
55                 {
56                     next.t++;
57                     vis[next.x][next.y]=true;
58                     q.push(next);
59                 }
60             }
61         }
62         
63     } 
64     return -1;
65 }
66 int main()
67 {
68     cin>>m;
69     int dx,dy,dt;
70     memset(a,INF,sizeof(a));//预处理
71     for(int i=0;i<m;i++)//预处理
72     {
73         cin>>dx>>dy>>dt;
74         a[dx][dy]=min(a[dx][dy],dt);//找最早被破坏的时间就是为了和主角到达的时间进行一个比较，看看当前主角有没有生命危险
75         for(int j=0;j<4;j++)
76         {
77             int nx,ny;
78             nx=dx+dir[j][0];
79             ny=dy+dir[j][1];
80             if(check(nx,ny))
81             {
82                 a[nx][ny]=min(a[nx][ny],dt);
83             }
84         }
85     }
86     cout<<bfs()<<endl;
87     return 0;
88 }

当然也有人说这是一道bfs求最短路的题目，有那个影子但是具体怎么操作我还是不太会；

网上大神给出的代码就当参考，集思广益吧

大神代码：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<cstdio>
 5 #define MAX_N 512
 6  
 7 using namespace std;
 8  
 9 int map[MAX_N][MAX_N];            //用于存储每个点最早被炸毁的时间 
10 bool visited[MAX_N][MAX_N];        //深度优先搜索时判定该点是否被访问过 
11 struct M{
12     int x,y,t;
13 };    //定义一个结构：代表着这点的坐标位置以及流星最早落下的时间 
14  
15 //要移动的方向：上 下 左 右 自身 
16 const int direction[5][2] = {
17     { -1, 0 },
18     { 1, 0 },
19     { 0, -1 },
20     { 0, 1 },
21     { 0, 0 },
22 };
23  
24 M m[50008];
25 int n;    //n个流星 
26 int last;    //最晚一颗流星落下的时间 
27  
28 int bfs(){
29     memset(visited,0,sizeof(visited));    //将每个点都初始化为未访问过 
30     queue<M> que;
31     M current;
32     current.x = 0;
33     current.y = 0;
34     current.t = 0;
35     que.push(current);                    //将原点（那人最初所在的点） 
36     while(que.size()){
37         const M mm = que.front();
38         que.pop();
39         for(int i = 0;i<4;i++){            //分别向四个方向移动 看看是否适合逃命 
40             current = mm;            
41             current.x = current.x + direction[i][0];
42             current.y = current.y + direction[i][1];
43             ++current.t;                //移动到一个方向代表着花费了一个时间 
44             if(current.x >= 0 && current.y>=0 && map[current.x][current.y] > current.t && !visited[current.x][current.y]){
45                 //map[current.x][current.y] > current.t代表着 爆炸时间 大于 当前时间 
46                 
47                 visited[current.x][current.y] = true;//访问过后设为true; 
48                 //在我看来下面的if是最难懂的，这代表着爆炸时间大于流星最晚落下时间 ，也就是这女孩已经逃离了流星的宠幸区
49                 //如果不离开的话她终将被宠幸。。好可怕。。所以她的最终目的就是逃离宠幸区
50                 //因为是广度优先搜索，所以到达这点的时间也就是最短的时间。 
51                 if(map[current.x][current.y] > last){
52                     return current.t;
53                 }
54                 //如果还没有到达安全区，则只是证明这点目前是安全的，加入到队列中去，看看该点周围是否有永久安全区。。 
55                 que.push(current);
56             }    
57         }
58     }
59     return -1;
60 }
61  
62  
63 int main()
64 {
65     cin>>n;
66     for(int i = 0;i<n;i++){
67         cin>>m[i].x>>m[i].y>>m[i].t; 
68     }
69     //将地图中每个点流星最晚落下的时间设为127（随便啦，满足题意就行）。。    
70     memset(map,0x7F,sizeof(map));
71     for(int i = 0;i<n;i++){
72         last = max(last,m[i].t);    //找出最后一颗流星落下的时间 
73         for(int j = 0;j < 5;j++){    //五个方向 
74             int nx = m[i].x+ direction[j][0];
75             int ny = m[i].y+ direction[j][1];
76             if(nx >= 0  && ny >= 0 && map[nx][ny] > m[i].t){    //保证map[][]中存的点位最早落下的时间 
77                 map[nx][ny] = m[i].t;
78             }            
79         }
80     }
81     if(map[0][0] == 0){            //如果还没开始逃命就被宠幸了，那就享受吧。。。 
82         cout<<"-1"<<endl;
83     }else{
84         cout<<bfs()<<endl;
85     }
86     return 0;    
87 }