首页 > 代码库 > bzoj1611[Usaco2008 Feb]Meteor Shower流星雨*
bzoj1611[Usaco2008 Feb]Meteor Shower流星雨*
bzoj1611[Usaco2008 Feb]Meteor Shower流星雨
题意：
给个网格，有m个流星，每个流星在ti时刻打在(xi,yi)的格子上，并把该格子和相邻的格子打烂。有个人从(0,0)出发，问最短逃离时间（格子被打烂之后就不能走）。
题解：
bfs一发，如果某格子被打烂的时间小于到达时间则不能到达，最后如果到达打烂时间为正无穷的格子即为成功逃出。注意网格的边界应该大于流星的边界，因为如果逃到那些地方也算安全地带。
代码：
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 500 7 #define INF 0x3fffffff 8 using namespace std; 9 10 inline int read(){11 char ch=getchar(); int f=1,x=0;12 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();}13 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar();14 return f*x;15 }16 int m,vis[maxn][maxn],ear[maxn][maxn]; queue<pair<int,int> >q;17 int bfs(){18 q.push(make_pair(1,1)); if(!ear[1][1])return -1;19 while(!q.empty()){20 int x=q.front().first,y=q.front().second; q.pop();21 if(x>1&&!vis[x-1][y]&&ear[x-1][y]>vis[x][y]+1){22 vis[x-1][y]=vis[x][y]+1; if(ear[x-1][y]==INF)return vis[x-1][y]; q.push(make_pair(x-1,y));23 }24 if(!vis[x+1][y]&&ear[x+1][y]>vis[x][y]+1){25 vis[x+1][y]=vis[x][y]+1; if(ear[x+1][y]==INF)return vis[x+1][y]; q.push(make_pair(x+1,y));26 }27 if(y>1&&!vis[x][y-1]&&ear[x][y-1]>vis[x][y]+1){28 vis[x][y-1]=vis[x][y]+1; if(ear[x][y-1]==INF)return vis[x][y-1]; q.push(make_pair(x,y-1));29 }30 if(!vis[x][y+1]&&ear[x][y+1]>vis[x][y]+1){31 vis[x][y+1]=vis[x][y]+1; if(ear[x][y+1]==INF)return vis[x][y+1]; q.push(make_pair(x,y+1));32 }33 }34 return -1;35 }36 int main(){37 m=read(); inc(i,0,400)inc(j,0,400)ear[i][j]=INF;38 inc(i,1,m){39 int x=read()+1,y=read()+1,z=read();40 inc(i,-1,1)ear[x+i][y]=min(ear[x+i][y],z),ear[x][y+i]=min(ear[x][y+i],z);41 }42 printf("%d",bfs()); return 0;43 }
20160917
bzoj1611[Usaco2008 Feb]Meteor Shower流星雨*
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。