求助

P2895 [USACO08FEB] Meteor Shower S

wyp20130701 @ 2024-11-14 17:49:07

#include <bits/stdc++.h>
using namespace std;
int ans[305][305], death[305][305];
void MIN(int x, int y, int t){
    if (x >= 0 && y >= 0) 
        death[x][y] = min(death[x][y], t);
    return;
}
struct coord{
    int x, y;
};
queue<coord> q;
int nxt[4][2] = {
    {0, 1},
    {1, 0},
    {0, -1},
    {-1, 0}
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    memset(ans, -1, sizeof(ans));
    memset(death, 0x7f, sizeof(death)); 
    for (int i = 1; i <= n; ++i){
        int x, y, t;
        cin >> x >> y >> t;
        MIN(x, y, t);
        for (int i = 0; i < 4; ++i) MIN(x + nxt[i][0], y + nxt[i][1], t);
    }
    q.push((coord){0, 0});
    ans[0][0] = 0;
    while (!q.empty()){
        coord now = q.front();
        q.pop();
        int x = now.x, y = now.y;
        for (int i = 0; i < 4; ++i){
            int ux = x + nxt[i][0], uy = y + nxt[i][1];
            if (ux < 0 || uy < 0 || ans[ux][uy] != -1 || ans[x][y] + 1 >= death[ux][uy]) continue;
            ans[ux][uy] = ans[x][y] + 1;
            q.push((coord){ux, uy}); 
        }
    }
    int Ans = INT_MAX;
    for (int i = 0; i <= 305; ++i)
        for (int j = 0; j <= 305; ++j)
            if (death[i][j] >= 100000 && ans[i][j] != -1)
                Ans = min(Ans, ans[i][j]);
    if (Ans == INT_MAX)
        puts("-1");
    else
        cout << Ans << "\n";
    return 0; 
}

就21分


by heyichen123 @ 2024-11-14 18:11:06

@wyp20130701 ??????


by wyp20130701 @ 2024-11-14 18:12:37

咋了?


|