求助,有大佬帮忙看看为什么第二个点Wa吗
查看原帖
求助,有大佬帮忙看看为什么第二个点Wa吗
249422
TinyMirror1楼主2020/9/21 16:32
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
long long s, ans[2];
int step[2003][2003];
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch ^ 48);
		ch = getchar();
	}
	return x * f;
}
struct node {
	int x, y, f;
	node(int xx, int yy, int ff) {
		f = ff, x = xx, y = yy;
	}
};
bool vis[2003][2003];
int Move[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
bool in(int x, int y) {
	return x >= 0 && x <= 2002 && y >= 0 && y <= 2002;
}
void bfs() {
	queue<node> q;
	q.push(node(1001, 1001, 0));
	vis[1001][1001] = true;
	while (!q.empty()) {
		node now = q.front();
		q.pop();
		step[now.x][now.y] = now.f;
		if (now.f <= s) ++ans[now.f & 1];
		for (int i = 0; i < 4; i++) {
			int tx = now.x + Move[i][0];
			int ty = now.y + Move[i][1];
			if (in(tx, ty) && !vis[tx][ty]) {
				q.push(node(tx, ty, now.f + 1));
				vis[tx][ty] = true;
			}
		}
	}
}
inline void stright(int step) {
	long long k = s - step;
	if (k <= 0) return;
	long long t = k >> 1;
	ans[step & 1] += t;
	ans[!(step & 1)] += k - t;
}
inline void corner(int step) {
	long long k = s - step;
	if (k <= 1) return;
	long long t = (k * k - k) / 2;
	if (k & 1) k--;
	long long x = (k * k) >> 2;
	ans[step & 1] += x;
	ans[!(step & 1)] += t - x;
}
int main() {
	int b = read();
	s = read();
	for (int i = 1; i <= b; ++i) {
		int x = read(), y = read();
		vis[x + 1001][y + 1001] = true;
	}
	bfs();
	for (int i = 0; i <= 2002; i++) {
		stright(step[0][i]);
		stright(step[i][0]);
		stright(step[2002][i]);
		stright(step[i][2002]);
	}
	corner(step[0][0]);
	corner(step[0][2002]);
	corner(step[2002][0]);
	corner(step[2002][2002]);
	cout << ans[0] << " " << ans[1];
	return 0;
}
2020/9/21 16:32
加载中...