https://www.luogu.com.cn/problem/P2895

肝搜索，肝完搜索肝dp

这道题调了半天SF，结果发现是判断上 “&&” 写成了 “，”，害我干瞪眼了1h

这道题我们先把 所有流星砸下来的时间先预处理，这里稍微用了点贪心的思想，因为我们是以从小到大的时间维护地图的，这样我们知道了每个点是在什么时候不能走的，然后就是一个普通的bfs了

我们每次去走一个点，判断能否赶得上流星，赶得上的话，我们就能走，而对于流星没砸的点，我们随便走。

还好一次A了，不然又要花1h来debug

AC代码

#include<bits/stdc++.h>

#define x first
#define y second

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1010,M = 5e4 + 10, INF = 0x3f3f3f3f;

int n;
int g[N][N];//我们的地图
bool unsafe[N][N];//是否安全
bool st[N][N];
int dx[] = {0,1,-1,0},dy[] = {1,0,0,-1};

struct Met
{
    int xx,yy,t;
    bool operator<(const Met&w) const//从小到大排序
    {
        return t < w.t;
    }
}met[M];

bool check(int x,int y)
{
    return (x >= 0 && y >= 0 && x < N && y < N);
}

void bfs(int a,int b)
{
    pii q[N * N];
    int hh = 0, tt = -1;
    st[a][b] = 1;
    q[++ tt] = {a,b};

    while(hh <= tt)
    {
        pii t = q[hh ++];
        for(int i = 0; i < 4; i ++)
        {
            int x = t.x + dx[i], y = t.y + dy[i];
            if(check(x,y) && !st[x][y])
            {
                if(unsafe[x][y])
                {
                    if(g[x][y] > g[t.x][t.y] + 1)//虽然危险，但我们赶得上
                    {
                        g[x][y] = g[t.x][t.y] + 1;
                        q[++ tt] = {x,y};
                        st[x][y] = 1;
                    }
                }
                else//安全的点，随便走
                {
                    g[x][y] = g[t.x][t.y] + 1;
                    q[++ tt] = {x,y};
                    st[x][y] = 1;
                }
            }
        }
    }
}

void work()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> met[i].xx >> met[i].yy >> met[i].t;
    sort(met,met + n);

    //预处理我们的流星在地图上的痕迹
    memset(g,0x3f,sizeof g);//初始化我们的地图没被砸过
    for(int i = 0; i < n; i ++)
    {
        if(g[met[i].xx][met[i].yy] == INF) g[met[i].xx][met[i].yy] = met[i].t;//没被砸过过，挑最短的时间砸
        unsafe[met[i].xx][met[i].yy] = 1;
        for(int j = 0; j < 4; j ++)
        {
            int t = met[i].t, x = met[i].xx + dx[j], y = met[i].yy + dy[j];
            unsafe[x][y] = 1;
            //还要砸上下左右四个点
            if(check(x,y) && g[x][y] == INF) g[x][y] = t;
        }
    }

    //第一个点就被砸了，直接寄（但这句话去掉也能A，有大佬告诉我为什么嘛？）
    if(g[0][0] == 0)
    {
        cout << -1 << endl;
        return;
    }

    g[0][0] = 0;
    bfs(0,0);

    //因为时间是1000，我们最多可以走到1000，所以这里直接举到1000就ok啦
    int ans = INF;
    for(int i = 0; i < 1010; i ++)
    {
        for(int j = 0; j < 1010; j ++)
        {
            if(!unsafe[i][j]) ans = min(ans,g[i][j]);
        }
    }
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    work();
    return 0;
}