3669:Meteor Shower

keyword

幅優先探索　C++

概要

2次元平面の原点に少女がいる。少女は第一象限を1秒に1マス動ける(4近傍のいずれか)。隕石がM(<50000)個降ってくる。隕石は(x_i, y_i) in [0..300]*[0..300]に時刻t_iに落ち、(x_i, y_i)とその4近傍の格子点にはそれ以後入ることが出来ない。少女が安全地帯(隕石の影響を受けないマス)に入るまでの最小時間を求める問題。
幅優先するだけ。ただし安全地帯は[0..302]*[0..302]の中から探さないといけないことに注意。何故か[0..301]*[0..301]でも通った。テストケースが弱かったんだと思う。計算量は、R=300としてO(R^2 + M)。

int xs[50001];
int ys[50001];
int ts[50001];
int board[310][310];
int dist[310][310];
int dx[] = {0,0,1,-1,0};
int dy[] = {1,-1,0,0,0};
int M;

bool isIn(int x, int y){
    return 0<=x && x<=301 && 0<=y && y<=301;
}

#define GET(xs,v) (xs[v.first][v.second])

int solve(){
    for(int i=0; i<M; i++){
        for(int k=0; k<5; k++){
            int ny = ys[i] + dy[k],
                nx = xs[i] + dx[k];
            if(isIn(nx,ny) && board[nx][ny] > ts[i]){
                board[nx][ny] = ts[i];
            }
        }
    }
    if(board[0][0] == INF)
        return 0;
    for(int i=0; i<=301; i++)
        for(int j=0; j<=301; j++)
            dist[i][j] = -1;
    queue<pint> Q;
    Q.push(make_pair(0,0));
    dist[0][0] = 0;
    while(!Q.empty()){
        pint tp = Q.front(); Q.pop();
        int time = GET(dist,tp) + 1;
        for(int k=0; k<4; k++){
            int ny = tp.second + dy[k],
                nx = tp.first + dx[k];
            if(isIn(nx,ny) && dist[nx][ny] == -1 && time < board[nx][ny]){
                if(board[nx][ny] == INF) return time;
                dist[nx][ny] = time;
                Q.push(make_pair(nx,ny));
            }
        }
    }
    return -1;
}