0分求助orz
查看原帖
0分求助orz
726139
残阳如血楼主2023/7/15 20:31

00 分代码,求调(悬赏关注

#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;
}
2023/7/15 20:31
加载中...