解题思路

在 的网格区域内，有 颗流星会坠落，第 颗流星会在 时刻坠落在 网格内。
流星坠落后，其所在的格子以及周围4个相邻的格子都化为焦土，无法行走。
现在有一个家族，在 0 时刻在 格子里，每1个时刻，他们能移动到相邻的 4 个格子中的任意一个。如果一个格子在时刻 t 被流星撞击或烧焦，那么他们只能在 t 之前的时刻在这个格子里出现。
求，这个家族是否在这场流星雨中幸存（移动到了一个没有被撞击或者烧焦的格子里一直待到流星雨结束），如果幸存，他们最少要花多少时间才移动到安全的格子里。
注：移动过程中 x 和 y 都可以超出300（但不能为负）。

本题使用 BFS 算法：
使用 fall 记录流星坠落后不能行走的网格以及时间。
使用队列实现 bfs()，从 (0,0) 出发，一旦到达的网格不在 fall 中，表示这个网格一直是安全的，即所求。

C++代码

#include<cstdio>
#include<map>
#include<queue>
#include<vector>
using namespace std;

const int N = 303;
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
map<pair<int,int>, int> fall;

int bfs(){
    if(fall.find(make_pair(0,0)) == fall.end())
        return 0;
    vector<vector<bool>> visited(N, vector<bool>(N, false));
    visited[0][0] = true;
    queue<pair<int,int>> que, que2, que3;
    que.push(make_pair(0,0));
    int t = 1;
    while(!que.empty()){
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        for(int i=0; i<4; ++i){
            int nx = x + d[i][0];
            int ny = y + d[i][1];
            if(nx >= 0 && ny >= 0){
                auto p2 = make_pair(nx, ny);
                if(fall.find(p2) == fall.end())
                    return t;
                if(visited[nx][ny]==false && fall[p2] > t){
                    que2.push(p2);
                    visited[nx][ny] = true;
                }
            }
        }
        if(que.empty()){
            que = que2;
            que2 = que3;
            ++t;
        }
    }
    return -1;
}

int main(){
    int M;
    scanf("%d", &M);
    int x, y, t;
    for(int i=0; i<M; ++i){
        scanf("%d%d%d", &x, &y, &t);
        auto p = make_pair(x,y);
        if(fall.find(p) == fall.end())
            fall[p] = t;
        else if(fall[p] > t)
            fall[p] = t;

        for(int i=0; i<4; ++i){
            auto p2 = make_pair(x+d[i][0], y+d[i][1]);
            if(fall.find(p2) == fall.end())
                fall[p2] = t;
            else if(fall[p2] > t)
                fall[p2] = t;
        }
    }

    int time = bfs();
    printf("%d\n", time);
    return 0;
}