QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#52984#2213. Knightnamelessgugugu#WA 17ms10372kbC++141.4kb2022-10-04 16:55:102022-10-04 16:55:24

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-04 16:55:24]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:10372kb
  • [2022-10-04 16:55:10]
  • 提交

answer

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 1005, M = 1000005;
int n, m, r, c;
char s[N][N];
int fa[M << 1], siz[M << 1];
inline int id(int x, int y)
{
	return (x - 1) * m + y;
}
inline void init(int l)
{
	for(int i = 1;i <= l;++i)
		fa[i] = i, siz[i] = 1;
	return;
}
int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y)
{
	x = find(x), y = find(y);
	if(x == y)
		return;
	if(siz[x] > siz[y])
		std::swap(x, y);
	fa[x] = y, siz[y] += siz[x];
	return;
}
int main(void)
{
	scanf("%d%d%d%d", &n, &m, &r, &c);
	for(int i = 1;i <= n;++i)
		scanf("%s", s[i] + 1);
	init(2 * n * m);
	for(int x = 1;x <= n;++x)
		for(int y = 1;y <= m;++y)
			if(s[x][y] != '@')
			{
				const int dx[8] = {r, r, -r, -r, c, c, -c, -c};
				const int dy[8] = {c, -c, c, -c, r, -r, r, -r};
				for(int o = 0;o < 8;++o)
				{
					int nx = x + dx[o], ny = y + dy[o];
					if(nx < 1 || nx > n || ny < 1 || ny > m || s[nx][ny] == '@')
						continue;
					merge(id(x, y), id(nx, ny) + n * m);
					merge(id(nx, ny), id(x, y) + n * m);
				}
			}
	int sa = 0, sb = 0;
	for(int i = 1;i <= n;++i)
		for(int j = 1;j <= m;++j)
			if(s[i][j] == 'A')
				sa = id(i, j);
			else if(s[i][j] == 'B')
				sb = id(i, j);
	if(find(sa) == find(sb + n * m))
		puts("Bob");
	else
		puts("Alice");
	return 0;
}

Details

Test #1:

score: 0
Wrong Answer
time: 17ms
memory: 10372kb