RE求调

P2895 [USACO08FEB] Meteor Shower S

ylx0527 @ 2024-11-30 17:35:25

#include<bits/stdc++.h>
using namespace std;
int m; 
struct note{
    int x, y, t;
};
note a[100000];
int cnt = -1;
int dx[5] = {0, 0, 1, 0, -1};
int dy[5] = {0, 1, 0, -1, 0};
int flag[500][500];
int dt[500][500];
void bfs(int xx, int yy, int tt){
    queue<note> q;
    flag[xx][yy] = 1;
    q.push((note){xx, yy, tt});
    while(!q.empty()){
        note to = q.front();
        q.pop();
        if(dt[to.x][to.y] == 1e9) {
            cnt = to.t;
            break;
        }
        for(int i = 1; i <= 4; i++){
            int xxx = to.x+dx[i];
            int yyy = to.y+dy[i];
            if(xxx >= 0 && yyy >= 0 && !flag[xxx][yyy] && to.t+1 < dt[xxx][yyy]){
                q.push((note){xxx, yyy, to.t+1});
//              cout << xxx << " " << yyy << " " << to.t+1 << endl;
                flag[xxx][yyy] = 1;
            }
        }
    }
}
int main(){
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    cin>>m;
    for(int i = 0; i <= 400; i++){
        for(int j = 0; j <= 400; j++){
            dt[i][j] = 1e9;
        }
    }
    for(int i = 1; i <= m; i++){
        cin >> a[i].x >> a[i].y >> a[i].t;
        dt[a[i].x][a[i].y] = a[i].t;
        for(int j = 1; j <= 4; j++){
            dt[a[i].x+dx[j]][a[i].y+dy[j]] = a[i].t;
        }
    }
    bfs(0, 0, 0);
    cout << cnt;
    return 0;
}

|