Algorithm_ZRF @ 2024-01-30 18:25:32

#include <bits/stdc++.h>
using namespace std;
const int maxm = 50005,maxn = 305;
int dx[] = {1,-1,0,0},
    dy[] = {0,0,1,-1};
struct meteor{
    int x,y,t;
}met[maxm];
int farm[maxn][maxn];
struct ss{
    int x,y,t;
};
int m;
inline void Read(){
    cin >> m;
    for(int i = 1;i <= m;++i){
        cin >> met[i].x >> met[i].y >> met[i].t; 
    }
}

inline int bfs(int x,int y,int t){
    queue<ss> q;
    ss s;//初始值
    s.x = x;
    s.y = y;
    s.t = t;
    q.push(s);
    priority_queue<int,vector<int>,less<int>> p;
    for(int i = 1;i <= m;++i){
        p.push(met[i].t);
    }
    int maxt = p.top();
    while(q.empty()){
        ss now = q.front();
        q.pop();
        for(int i = 1;i <= m;++i){
            if(now.t == met[i].t){
                farm[met[i].x][met[i].y] = 1;
                farm[met[i].x+1][met[i].y] = 1;
                farm[met[i].x-1][met[i].y] = 1;
                farm[met[i].x][met[i].y+1] = 1;
                farm[met[i].x][met[i].y-1] = 1; 
            }
        }
        if(now.t == maxt && farm[now.x][now.y] == 1){
            break;
        }
        if(now.t == maxt && farm[now.x][now.y] == 1){
            return now.t;
        }
        for(int i = 0;i < 4;++i){
            int tx = now.x + dx[i],
                ty = now.y + dy[i],
                tt = now.t + 1;
            if(tx < 0 || ty < 0) continue;//判断越界
            if(farm[tx][ty] == 1)continue;//判断此地是否有陨石砸过
            if(farm[tx][ty] == 2)continue;//判断此地是否已经走过
            farm[tx][ty] = 2; 
            q.push({tx,ty,tt}); 
        }
    } 
    return -1;
}

inline void solve(){
    Read();
    cout << bfs(0,0,0);
}

signed main(){
    solve();
    exit(0);
}

by Algorithm_ZRF @ 2024-01-30 19:15:43

@xu_zhihao @yaodiguoan

by danlao @ 2024-01-30 19:28:40

@Algorithm_ZRF 题目是先读入t再读入x,y的

inline void Read(){
    cin >> m;
    for(int i = 1;i <= m;++i){
        cin >> met[i].x >> met[i].y >> met[i].t; 
    }
}

by danlao @ 2024-01-30 19:31:52

@Algorithm_ZRF 你的数组开小了，牛是可以走到\left(300,300\right)以外的

by Algorithm_ZRF @ 2024-02-17 11:56:01

@yaodiguoan 改了，全RE

by danlao @ 2024-02-17 12:01:53

@Algorithm_ZRF 请你跟我这样写

#include <iostream>
#include <queue>
using namespace std;
#define hh printf("\n")
#define kg printf(" ")
#define cg ch=getchar()
inline int read(){
    int x=0,f=1;char cg;
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;cg;}
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';cg;}
    return x*f;
}
inline void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
int dx[5]={0,-1,0,1,0};
int dy[5]={0,0,-1,0,1};
int n,map[510][510],maxt,inf=2147483647;
bool vis[510][510];
struct csp{
    int x,y,t;
};
int bfs(int x,int y,int t){
    queue<csp>q;
    q.push((csp){x,y,t});
    while(!q.empty()){
        x=q.front().x;
        y=q.front().y;
        t=q.front().t;
        q.pop();
        if(vis[x][y]) continue;
        vis[x][y]=1;
        if(map[x][y]==inf) return t;
        for(int i=1;i<=4;i++){
            int tx=x+dx[i];
            int ty=y+dy[i];
            if(tx>=0&&ty>=0&&tx<=500&&ty<=500&&map[tx][ty]>t+1) q.push((csp){tx,ty,t+1});
        }
    }
    return -1;
}
int main(){
    for(int i=0;i<=500;i++)
        for(int j=0;j<=500;j++)
            map[i][j]=inf;
    n=read();
    for(int i=1;i<=n;i++){
        int x=read(),y=read(),t=read();
        map[x][y]=min(map[x][y],t);
        maxt=max(maxt,t);
        for(int j=1;j<=4;j++){
            int tx=x+dx[j];
            int ty=y+dy[j];
            if(tx>=0&&ty>=0) map[tx][ty]=min(map[tx][ty],t);
        }
        if(!map[0][0]) {
            write(-1);
            return 0;
        }
    }
    write(bfs(0,0,0));
    return 0;
}