传送门

题目描述：

牛去看流星雨，不料流星掉下来会砸毁上下左右中五个点。每个流星掉下的位置和时间都不同，求牛能否活命，如果能活命，最短的逃跑时间是多少？

Sample Input

4 
0 0 2 
2 1 2 
1 1 2 
0 3 5

Sample Output

5

HINT

      t = 0                t = 2              t = 5
5|. . . . . . .     5|. . . . . . .     5|. . . . . . .    
4|. . . . . . .     4|. . . . . . .     4|# . . . . . .   * = meteor impact
3|. . . . . . .     3|. . . . . . .     3|* # . . . . .  
2|. . . . . . .     2|. # # . . . .     2|# # # . . . .   # = destroyed pasture
1|. . . . . . .     1|# * * # . . .     1|# # # # . . .   
0|B . . . . . .     0|* # # . . . .     0|# # # . . . .   
  --------------      --------------      -------------- 
  0 1 2 3 4 5 6       0 1 2 3 4 5 6       0 1 2 3 4 5 6

5|. . . . . . . 
4|. . . . . . . 
3|3 4 5 . . . .  Bessie's locations over time 
2|2 . . . . . .  for one solution 
1|1 . . . . . . 
0|0 . . . . . . 
  -------------- 
  0 1 2 3 4 5 6

思路：

因为流星掉落时间确定，所以本题就是让我们找一个流星砸不到的地方。
我们可以先预处理出所有流星掉落后哪些地不能走，然后再搜索；
一个点能被到达的条件是：当牛到达这个点时没有被流星砸毁，或永远也不会被流星砸毁（答案）
注意：本题中流星掉落时间可为0，所以我们要将预处理数组设为-1；

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
bool book[2000][2000];
int a[2100][2100];
int dx[6]={0,1,-1,0,0,0};
int dy[6]={0,0,0,1,-1,0};
struct your
{
    int x,y,step;
};
void make(int x,int y,int t)
{
    for(int i=1;i<=5;i++)
    {
        int dxx=x+dx[i];
        int dyy=y+dy[i];
        if(dxx>=0&&dyy>=0)
        {
            if(a[dxx][dyy]==-1)
                a[dxx][dyy]=t;
            else a[dxx][dyy]=min(a[dxx][dyy],t);
        }
    }   
}
void bfs()
{
    queue<your>q;
    book[0][0]=1;
    your nmp;
    nmp.x=nmp.y=0,nmp.step=0;
    q.push(nmp);
    while(q.size())
    {
        nmp=q.front();q.pop();
        for(int i=1;i<=4;i++)
        {
            int dxx=nmp.x+dx[i];
            int dyy=nmp.y+dy[i];
            if(dxx<0||dyy<0) continue;
            if(a[dxx][dyy]==-1)
            {
                printf("%d",nmp.step+1);
                return ;
            }
            if(book[dxx][dyy]==0&&a[dxx][dyy]>nmp.step+1)
            {
                your temp;
                temp.x=dxx,temp.y=dyy;
                temp.step=nmp.step+1;
                q.push(temp);
                book[dxx][dyy]=1;
            }
        }
    }
    printf("-1");
}
int main()
{
    memset(a,-1,sizeof a);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,y,t;
        scanf("%d%d%d",&x,&y,&t);
        make(x,y,t);
    }
    bfs();
}