POJ 3669 Meteor Showerをbfsを使わずに解いてみるよ！

POJ3669といえば蟻本初級編章末でbfs問題として紹介されている。
事実bfsで解けるし、そのコードはこれが綺麗。今回の解法でも非常に参考になった。

さて、この問題、以前東方AIに使ったDP的な方法で解けるように見えた。
つまり移動可能な領域を探索深さが進むにつれ拡張（場合によっては縮小）していくことで、深さtにおいてある地点に移動可能かどうか知るという方法である。

#include <iostream>
#include <stdio.h>
using namespace std;

const int INF = 100000000;
const int N = 310;
const int MAX_T = 1000;
int grid[N][N];
bool dist[N][N][2];
int dx[] = {0, 0, 0, 1, -1};
int dy[] = {0, 1, -1, 0, 0};

int solve(){
    if(grid[1][1] == 0)
        return -1;
    dist[1][1][0] = true;
    for(int t=1; t<MAX_T; t++)for(int i=1; i<N-1; i++)for(int j=1; j<N-1; j++){
        if(dist[i][j][(t+1)%2]){
            for(int d=0; d<5; d++){
                int nx = i+dx[d], ny = j+dy[d];
                if(t < grid[nx][ny]){
                    dist[nx][ny][t%2] = true;
                    if(grid[nx][ny] == INF)
                        return t;
                }else{
                    dist[nx][ny][t%2] = false;
                }
            }
        }
    }
    return -1;
}

int main(int argc, const char * argv[]){
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            grid[i][j] = INF;
    for(int i=0; i<N; i++){
        grid[0][i] = 0;
        grid[i][0] = 0;
    }
    int M;
    scanf("%d", &M);
    int X, Y, T;
    for(int m=0; m<M; m++){
        scanf("%d%d%d", &X, &Y, &T);
        X++; Y++;
        for(int d=0; d<5; d++){
            int& g = grid[X+dx[d]][Y+dy[d]];
            g = min(g, T);
        }
    }
    printf("%d\n", solve());
    return 0;
}

このアルゴリズムの計算量はO(N * N * T), N=高さ, 幅, T = 最大深さである。一般にbfsの計算量は状態数×遷移数であるが、これも同様にO(N * N * T * 5)でよく一致している。

この方法は実は典型的なdfs問題である迷路の最短経路問題でも用いることが出来る。
しかし、この場合も安直に移動可能領域を更新するなら同様に計算量はO(N * N * T)である。一方bfsではO(N * N * 4)で圧倒的に速い。

これは簡単な枝刈りで解消される。迷路問題の場合、更新される移動可能領域は必ずその領域のエッジ部（移動可能領域と不可領域の境界）である。このエッジ部をqueueに入れて管理すればbfsと全く同様の動きをすることが分かる（深さがイメージしやすい分bfsの理解がしやすいかも？）。

復習をすると新たな気付きがあって良い。