BFS

依据题目自定义图上点的特殊属性

用BFS需要利用一些特殊信息来防止重复走

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

#include <bits/stdc++.h>
#define debug(x) cout<<"!"<<(x)<<"!"<<endl
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;

const int N = 400 ;
int g[N][N] ;
typedef pair<int,int> PII;

int m;
int d[N][N];

int bfs(int x , int y){
    memset(d,-1,sizeof d);
    d[x][y] = 0;

    queue<PII> q;
    q.push({x,y});
    int dx[] = {-1,0,1,0};
    int dy[] = {0,1,0,-1};
    if(g[x][y]==0x3f3f3f3f) return 0;

    while(q.size()){
        auto k = q.front();
        q.pop();
        int ttt = d[k.first][k.second] + 1;//扩展其他位置的时间刻
        for(int i = 0 ; i < 4 ; i++){
            int a = k.first + dx[i];
            int b = k.second + dy[i];

            if(a>= 0 && b >= 0 && d[a][b]==-1 && (ttt < g[a][b])){

                if(g[a][b]==0x3f3f3f3f){
                    return ttt;
                }
                d[a][b] = ttt;
                q.push({a,b});                  

            }
        }
    }

    return -1;

}

int main(){
    memset(g,0x3f,sizeof g);

    cin >> m;
    int dx[] = {-1,0,1,0};
    int dy[] = {0,1,0,-1};

    for(int i = 0 ; i < m; i++){
        int x , y , t;
        cin >> x >> y >> t;
        g[x][y] = min(g[x][y],t);//每个格备注被砸到的最小时间
        for(int j = 0 ; j < 4 ; j++){
            int a = x +dx[j];
            int b = y +dy[j];
            if(a >= 0 && a <= 300 && b >= 0 && b <= 300){
                g[a][b] = min(g[a][b],t);
            }
        }
    }
    cout << bfs(0,0);
}