This post is written in Chinese. Please consider using Google Translate

动态规划

该题满足满足动态规划的无后效性和最优子结构，但是对于最大情况，有3003001000个状态。由于状态过多且无法压缩，只好搜索。(不排除有压缩的方法)

搜索

由于此题求得是最少花费的时间，所以最好用广度优先搜索是一种较好的方法，直接的BFS可以通过。而DFS需要加优化才能通过。

以时间为阶段划分，记录当前点所在的坐标。每次产生式规则都有上下左右四种可能，对于走到流星雨的位置上的点要去除。

在初始化阶段，算出最终的“安全点”，即流星雨结束以后没有被砸的点。搜索中第一次走到了安全点，就是最少需要的时间。

/*
ID: cmykrgb1
PROG: meteor
LANG: C++
*/

#include <iostream>
#define MAX 302
#define MAXT 50001
using namespace std;

typedef struct
{
    int x,y,t;
}star;

class tQueue
{
public:
    class linklist
    {
    public:
        linklist* next;
        star value;
        linklist()
        {
            next=0;
        }
    };
    linklist *first,*last;
    bool used[MAX][MAX];
    int size;
    void add(star p)
    {
        if (size==0)
            first=last=new linklist;
        else
            last=last->next=new linklist;
        last->value=p;
        size++;
        used[p.x][p.y]=true;
    }
    star del()
    {
        star rtn=first->value;
        linklist *tfirst=first;
        first=first->next;
        delete tfirst;
        size--;
        used[rtn.x][rtn.y]=false;
        return rtn;
    }
    void reset()
    {
        size=0;
        first=last=0;
        memset(used,0,sizeof(used));
    }
    tQueue()
    {
        reset();
    }
};

star S[MAXT];
bool Die[MAX][MAX];
bool Map[MAX][MAX];
bool F[MAX][MAX];
int N;
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
tQueue Q;

inline int cmp(const void *a,const void *b)
{
    return ((star *)a)->t - ((star *)b)->t;
}

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

void put(int i,bool M[][MAX])
{
    if (i==0)return;
    int x=S[i].x,y=S[i].y;
    if (inrange(x,y))
        M[x][y]=true;
    if (inrange(x+1,y))
        M[x+1][y]=true;
    if (inrange(x-1,y))
        M[x-1][y]=true;
    if (inrange(x,y+1))
        M[x][y+1]=true;
    if (inrange(x,y-1))
        M[x][y-1]=true;
}

void init()
{
    int i;
    freopen("meteor.in","r",stdin);
    freopen("meteor.out","w",stdout);
    cin >> N;
    for (i=1;i<=N;i++)
    {
        cin >> S[i].x >> S[i].y >> S[i].t;
        put(i,Die);
    }
    qsort(S+1,N,sizeof(S[0]),cmp);
    S[N+1].t=S[N].t+1;
}

int bfs()
{
    int i,j=0,T;
    star F,Y;
    F.x=F.y=F.t=0;
    Q.add(F);
    while (Q.size)
    {
        F=Q.del();
        if (!Die[F.x][F.y])
            return F.t;
        Y.t=F.t+1;
        if (Y.t>S[j].t)
        {
            while (Y.t>S[j].t)
                put(j++,Map);
        }
        if (Map[F.x][F.y])
            continue;
        for (i=0;i<4;i++)
        {
            Y.x=F.x+dx[i];
            Y.y=F.y+dy[i];
            if (inrange(Y.x,Y.y) && !Map[Y.x][Y.y] && !Q.used[Y.x][Y.y])
            {
                Q.add(Y);
            }
        }
    }
    return -1;
}

int main()
{
    int Ans;
    init();
    Ans=bfs();
    cout << Ans << endl;
    return 0;
}