POJ 3669（优先队列BFS)(对地图进行优化)

本文主要是介绍POJ 3669（优先队列BFS)(对地图进行优化)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目新颖，解法也是比较难想的。

题目：

Bessie听说有场史无前例的流星雨即将来临；有谶言：陨星将落，徒留灰烬。为保生机，她誓将找寻安全之所（永避星坠之地）。目前她正在平面坐标系的原点放牧，打算在群星断其生路前转移至安全地点。

此次共有M (1 ≤ M ≤ 50,000)颗流星来袭，流星i将在时间点Ti (0 ≤ Ti  ≤ 1,000) 袭击点 (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300)。每颗流星都将摧毁落点及其相邻四点的区域。

Bessie在0时刻时处于原点，且只能行于第一象限，以平行与坐标轴每秒一个单位长度的速度奔走于未被毁坏的相邻（通常为4）点上。在某点被摧毁的刹那及其往后的时刻，她都无法进入该点。

寻找Bessie到达安全地点所需的最短时间。

Input - 输入

* 第1行: 一个整数: M
* 第2..M+1行: 第i+1行包含由空格分隔的三个整数: Xi, Yi, and Ti

Output - 输出

* 仅一行: Bessie寻得安全点所花费的最短时间，无解则为-1。

Sample Input - 输入样例

4
0 0 2
2 1 2
1 1 2
0 3 5

Sample Output - 输出样例

5

代码：

#include<stdio.h>
#include<iostream>
using namespace std;
#include<stdio.h>
#include<string>
#include<queue>
#include<string.h>
int s[4]={0,0,1,-1};
int s1[4]={1,-1,0,0};
const int maxn=310;
int a[maxn][maxn];    //地图 
int vis[maxn][maxn];  //标记数组 
typedef long long ll;typedef struct node
{int x,y,time;bool operator< (const node&b)const {return time > b.time;}
}point;int min(int a,int b)
{return a>b?b:a;
}void bfs(int x,int y)
{memset(vis,0,sizeof(vis));priority_queue<point>q;point t;t.x=x;t.y=y;t.time=0;q.push(t);vis[x][y]=1;while(!q.empty()){point s2=q.top();q.pop();if(a[s2.x][s2.y]==-1){printf("%d\n",s2.time);return ;}for(int i=0;i<4;i++){point temp;temp.x=s2.x+s[i];temp.y=s2.y+s1[i];temp.time=s2.time+1;if(temp.x>=0&&temp.y>=0&&(a[temp.x][temp.y]==-1||a[temp.x][temp.y]>temp.time)){if(!vis[temp.x][temp.y])q.push(temp);vis[temp.x][temp.y]=1;}}}printf("-1\n");
}
int main()
{int n;while(scanf("%d",&n)!=EOF){int x,y,time;memset(a,-1,sizeof(a));for(int i=0;i<n;i++){scanf("%d%d%d",&x,&y,&time);//cin>>x>>y>>time;if(a[x][y]==-1)a[x][y]=time;elsea[x][y]=min(time,a[x][y]);for(int j=0;j<4;j++){int xx=x+s[j];int yy=y+s1[j];if(xx>=0&&yy>=0){if(a[xx][yy]==-1)a[xx][yy]=time;elsea[xx][yy]=min(a[xx][yy],time);}}}bfs(0,0);}return 0;
}

代码首先是把地图先处理一遍，因为有要求，流行爆炸过的地方不能走，和几秒后流行爆炸的地方是不能走的（在爆炸之前走过去）。对地图进行初始值操作地图全为 -1，流星炸过（将要炸）的地方标记为爆炸的时间，并且前后左右四个方向都会遭殃，也标记为爆炸时间，如果爆炸地点重复，就更新为最短的时间。这道题目的特殊性是先进行标记处理，然后再去BFS搜索最短的时间，因为有一些爆炸过的点作为障碍，就用优先队列（好像普通的队列也可以）对时间进行最小的排序，得到最小时间。

总结：对地图有一些更高的要求，就事先处理地图，处理好后，再进行BFS操作，又是一个新的思路，事先处理好地图的相关操作。

这篇关于POJ 3669（优先队列BFS)(对地图进行优化)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---