21pts求助

P2895 [USACO08FEB] Meteor Shower S

__UrFnr__ @ 2024-07-16 10:08:05

只有三个点AC,其他11个点全部RE

代码:

#include <bits/stdc++.h>
using namespace std;
#define maxn 310
struct coord {
    int x, y;
};
queue <coord> q;
int ans[maxn][maxn], death[maxn][maxn];
int wk[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
void MIN (int x, int y, int t) {
    if (x >= 0 && y >= 0) 
        death[x][y] = min (death[x][y], t);
}
int main () {
    int m, Ans = 100000;
    memset (ans, -1, sizeof (ans));
    memset (death, 0x7f, sizeof (death));
    cin >> m;
    for (int i = 1; i <= m; i ++) {
        int x, y, t;
        cin >> x >> y >> t;
        MIN (x, y, t);
        for (int k = 0; k < 4; k ++) 
            MIN (x + wk[k][0], y + wk[k][1], t); 
    }
    q.push ((coord) {0, 0});
    ans[0][0] = 0;
    while (! q.empty ()) {
        coord u = q.front ();
        int ux = u.x, uy = u.y;
        q.pop ();
        for (int k = 0; k < 4; k ++) {
            int x = ux + wk[k][0], y = uy + wk[k][1];
            if (x < 0 || y < 0 || ans[x][y] != -1 || ans[ux][uy] + 1 >= death[x][y]) 
                continue;
            ans[x][y] = ans[ux][uy] + 1;
            q.push ((coord) {x, y});
        }
    }
    for (int i = 0; i <= 305; i ++) 
        for (int j = 0; j <= 305; j ++) 
            if (death[i][j] > 1000 && ans[i][j] != -1) 
                Ans = min (Ans, ans[i][j]);
    if (Ans == 100000) 
        puts ("-1");
    else 
        printf ("%d", Ans);
}

|