0 分代码,求调(悬赏关注
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 1 << 14;
int M, t, p, now[400][400], safe[400][400], ans[400][400];
int walk[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
struct meteor {
int X, Y, T;
} danger[50010];
struct place {
int x, y;
};
char getc() {
static char buf[SIZE], *begin = buf, *end = buf;
if (begin == end) {
begin = buf;
end = buf + fread(buf, 1, SIZE, stdin);
}
return *begin++;
}
int read() {
int sgn = 0, ret = 0, ch = getc();
while (!isdigit(ch) && ch != EOF) ch |= ch == '-', ch = getc();
while (isdigit(ch) && ch != EOF) ret = ret * 10 + ch - '0', ch = getc();
return sgn ? -ret : ret;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
return;
}
bool cmp(meteor a, meteor b) {
if (a.T == b.T) {
if (a.X == b.X) return a.Y < b.Y;
return a.X < b.X;
}
return a.T < b.T;
}
bool inRange(int x, int y) {
if (x < 0 || y < 0) return false;
return true;
}
int main() {
queue<place> q;
cin >> M;
memset(safe, -1, sizeof(safe));
for (int i = 0; i < M; i++) {
danger[i].X = read(), danger[i].Y = read(), danger[i].T = read();
safe[danger[i].X][danger[i].Y] = 0;
for (int k = 0; k < 4; k++) {
int newx = danger[i].X + walk[k][0];
int newy = danger[i].Y + walk[k][1];
if (!inRange(newx, newy)) continue;
safe[newx][newy] = 0;
}
}
sort(danger, danger + M, cmp);
q.push({0, 0});
ans[0][0] = 1;
while (!q.empty()) {
auto cur = q.front();
q.pop();
while (danger[p].T == t)
now[danger[p].X][danger[p].Y] = -1, p++;
t++;
if (safe[cur.x][cur.y]) {
cout << ans[cur.x][cur.y] - 1;
return 0;
}
for (int i = 0; i < 4; i++) {
int newx = cur.x + walk[i][0];
int newy = cur.y + walk[i][1];
if (!inRange(newx, newy)) continue;
if (ans[newx][newy] || now[newx][newy] == -1) continue;
q.push({newx, newy});
ans[newx][newy] = ans[cur.x][cur.y] + 1;
}
}
cout << -1;
return 0;
}