__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);
}