POJ 3669 - Meteor Shower

問題概要

少女が座標(0,0)のマスにいる。少女は隣接する4つのマスに移動できる。今、M個の隕石が落下する。各隕石は座標(X,Y)のマスに時刻Tのとき落下し、落下したマスとその隣接する4つの座標が通行できなくなる。この条件の下、少女が安全なマス(隕石の影響を受けない座標)に到達するための最小時間を求めよ。ただし、到達できない場合は-1を出力せよ。

制約

• 1 ≤ M ≤ 50000
• 0 ≤ X ≤ 300
• 0 ≤ Y ≤ 300
• 0 ≤ T ≤ 1000

解法

bfsする。探索範囲に注意が必要。

コード

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>

using namespace std;

#define MAX 310
#define INF 1e9

int field[MAX][MAX];
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};

struct P{
  int x,y,d;
  P(int x,int y,int d) : x(x),y(y),d(d) {}
};

bool inField(int x,int y){
  return (0 <= x && x < MAX && 0 <= y && y < MAX);
}

int solve(){
  queue<P> Q;
  Q.push(P(0,0,0));
  bool visited[MAX][MAX];
  memset(visited,false,sizeof(visited));
  visited[0][0] = true;
  while(!Q.empty()){
    P p = Q.front(); Q.pop();
    if(field[p.y][p.x] == INF){
      return p.d;
    }
    for(int i = 0 ; i < 4 ; i++){
      int nx = p.x + dx[i];
      int ny = p.y + dy[i];
      if(!inField(nx,ny)){ continue; }
      if(p.d + 1 >= field[ny][nx]){ continue; }
      if(visited[ny][nx]){ continue; }
      visited[ny][nx] = true;
      Q.push(P(nx,ny,p.d+1));
    }
  }
  return -1;
}

int main(){
  int M,X,Y,T;
  fill(field[0],field[0]+MAX*MAX,INF);
  scanf("%d",&M);
  while(M--){
    scanf("%d%d%d",&X,&Y,&T);
    field[Y][X] = min(field[Y][X],T);
    for(int i = 0 ; i < 4 ; i++){
      int nx = X + dx[i];
      int ny = Y + dy[i];
      if(inField(nx,ny)){
        field[ny][nx] = min(field[ny][nx],T);
      }
    }
  }
  printf("%d\n",solve());
  return 0;
}