【POJ 3669 Meteor Shower】简单BFS

时间:2023-12-29 14:56:14

流星雨撞击地球(平面直角坐标第一象限),问到达安全地带的最少时间。

对于每颗流星雨i,在ti时刻撞击(xi,yi)点,同时导致(xi,yi)和上下左右相邻的点在ti以后的时刻(包括t)不能再经过(被*)。安全地带为永远不会被*的点。

简单bfs,开始WA在把平面空间上限当成300*300,但根据题目,这只是有流星雨撞击的范围。实际可走的空间理论上没上限,但分析可得,离原点最近的安全地带一定在(302,302)范围内,所以应可把数组至少开为303*303。

后来WA在把G[0][0]==1的情况也归为无解了。这是没想清楚预处理的意义。。。

 #include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std; const int INF=;
const int MAX_N=;//流星雨落在(300,300)以内,所以最近的安全点一定在(302,302)以内
int m;
int G[MAX_N+][MAX_N+];
int dx[]={,,,-},dy[]={,-,,};
int vis[MAX_N+][MAX_N+]; struct Node
{
int x,y,time;
Node(){}
Node(int xx,int yy,int t):x(xx),y(yy),time(t){}
}; int inside(int x,int y)
{
if(x<||y<||MAX_N<x||MAX_N<y) return ;
else return ;
} int bfs()
{
memset(vis,,sizeof(vis));
if(G[][]==INF) return ;
if(G[][]==) return -;//当G[0][0]==1时,不代表没希望逃走。。。
//因为G数组经过预处理了,把每颗流星雨的影响都表达为每个点的*时间
queue<Node> que;
que.push(Node(,,));
vis[][]=;
while(!que.empty())
{
Node cur=que.front();
que.pop();
if(G[cur.x][cur.y]==INF) return cur.time;
for(int i=;i<;i++)
{
int nx=cur.x+dx[i];
int ny=cur.y+dy[i];
if(!inside(nx,ny)) continue;
if(vis[nx][ny]) continue;
if(G[nx][ny]<=cur.time+) continue;
que.push(Node(nx,ny,cur.time+));
vis[nx][ny]=;
}
}
return -;
} int main()
{
freopen("3669.txt","r",stdin);
scanf("%d",&m);
for(int i=;i<=MAX_N;i++)
for(int j=;j<=MAX_N;j++)
G[i][j]=INF;
for(int i=;i<m;i++)
{
int x,y,t;
scanf("%d%d%d",&x,&y,&t);
G[x][y]=min(t,G[x][y]);
for(int i=;i<;i++)
{//把G数组预处理为每个点的最早*时间
int nx=x+dx[i];
int ny=y+dy[i];
if(!inside(nx,ny)) continue;
G[nx][ny]=min(t,G[nx][ny]);
}
}
printf("%d\n",bfs());
return ;
}

还是考虑问题不全面不清晰啊。。。多做题多总结吧