本文主要是介绍POJ 3669 Meteor Shower (BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://poj.org/problem?id=3669
题意：有一场流星雨要降临，有个倒霉鬼要躲避流星雨。给出流星雨的降落位置和时间，每一个流星雨降临会造成上下左右的附加伤害，流行砸到过的地方不能再去。这个倒霉鬼以每秒一个距离单位的速度可以向上下左右四个方向逃跑，求他能不能逃掉。不能输出-1，能的话输出最短时间。
题解：BFS。用时间来初始化状态数组，进行BFS的时候判断一下时间即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAX=300+10;
const int INF=0x3f3f3f3f;
int a[MAX][MAX];
int d[MAX][MAX];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
typedef pair<int,int> P;
int bfs()
{if(a[0][0]==0) {return -1;}memset(d,0x3f,sizeof(d));queue<P> que; que.push(P(0,0));d[0][0]=0;while(!que.empty()){int x=que.front().first;int y=que.front().second;que.pop();if(a[x][y]==INF) {return d[x][y];break;}for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx>=0&&ny>=0&&a[nx][ny]>d[x][y]+1&&d[nx][ny]==INF){d[nx][ny]=d[x][y]+1;que.push(P(nx,ny));}}}if(que.empty())return -1;
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int m;while(scanf("%d",&m)!=EOF){memset(a,0x3f,sizeof(a));for(int i=0;i<m;i++){int x,y,t;scanf("%d%d%d",&x,&y,&t);a[x][y]=min(a[x][y],t);for(int j=0;j<4;j++){int nx=x+dx[j];int ny=y+dy[j];if(nx>=0&&ny>=0){a[nx][ny]=min(a[nx][ny],t);//如果重复被炸，应该取先被炸的}}}int ans=bfs();printf("%d\n",ans);}return 0;
}这篇关于POJ 3669 Meteor Shower (BFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
