USACO FEB08 Problem 'meteor' Analysis

by Richard Peng

For each point on the farm, we can compute the time where it will first be destroyed. Notice that there is no point not going into a point at the earliest time we could since if we're safe at a location in time t, we're also safe at time t-1 at that location. Then the problem becomes computing the shortest path from a the starting point to any point which will never be destroyed.

We accomplish this by doing a breadth-first-search from the starting point. The only modification we need to make is to only add points whose earliest time reachable is earlier than the time the point is destroyed.

Rob points out that one can do a normal flood fill on the plane after sorting the meteors so that you can destroy plane elements as each meteor arrives on its schedule.

The data were generated placing meteors in certain patterns to force Bessie to take certain paths.

Here is my implementation, which used a rather entertaining choice of variable names:

#include <cstdio>
#include <cstring>
#include <cstdlib>

int kaboom[500][500],n,huge,q[150000][2],tail,dis[500][500];
int dir[4][2]={-1,0,1,0,0,-1,0,1};

void moo(int x,int y,int d){
  if((x>=0)&&(y>=0)&&(d<kaboom[x][y])&&(d<dis[x][y])){
    if(kaboom[x][y]==huge){
      printf("%d\n",d);
      exit(0);
    }
    dis[x][y]=d;
    q[tail][0]=x;
    q[tail++][1]=y;
  }
}

int main(){
  int i,j,a,b,t;
  huge=1<<20;
  freopen("meteor.in","r",stdin);
  freopen("meteor.out","w",stdout);
  scanf("%d",&n);
  for(i=0;i<500;i++)
    for(j=0;j<500;j++)
      dis[i][j]=kaboom[i][j]=huge;
  for(i=0;i<n;i++){
    scanf("%d%d%d",&a,&b,&t);
    kaboom[a][b]<?=t;
    if(a>0) kaboom[a-1][b]<?=t;
    if(b>0) kaboom[a][b-1]<?=t;
    kaboom[a+1][b]<?=t;
    kaboom[a][b+1]<?=t;
  }
  tail=0;
  moo(0,0,0);
  for(i=0;i<tail;i++)
    for(j=0;j<4;j++)
      moo(q[i][0]+dir[j][0],q[i][1]+dir[j][1],dis[q[i][0]][q[i][1]]+1);
  puts("-1");
  return 0;
}