QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#113953#2213. KnightyanranRE 0ms0kbC++141.4kb2023-06-20 10:56:232023-06-20 10:56:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-20 10:56:24]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-06-20 10:56:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int read() {
    int x = 0; char ch = getchar();
    while (ch < '0') ch = getchar();
    while (ch >= '0') x = x * 10 + ch - 48, ch = getchar();
    return x;
}

const int N = 1003;
int n, m, r, c, A, B, fa[N], col[N];
char s[N][N];
vector<int> e[N * N];

inline int id(int x, int y) {
	return (x - 1) * m + y;
}
inline int find(int x) {
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void link(int a, int x, int y) {
	if (x > n || y > m || y < 1 || s[x][y] == '@') return;
	int b = id(x, y);
	e[a].push_back(b), e[b].push_back(a);
	fa[find(a)] = find(b);
}

void dfs(int u, int co) {
	col[u] = co;
	for (int v : e[u]) if (!col[v]) dfs(v, co ^ 1);
}

int main() {
	n = read(), m = read(), r = read(), c = read();
	for (int i = 1; i <= n; i++) scanf("%s", s[i] + 1);

	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (s[i][j] == '@') continue;
			if (s[i][j] == 'A') A = id(i, j);
			if (s[i][j] == 'B') B = id(i, j);
			int u = id(i, j);
			link(u, i + r, j + c);
			link(u, i + r, j - c);
			link(u, i + c, j + r);
			link(u, i + c, j - r);
		}
	}
	if (e[A].size() == 1 && e[A][0] == B) {
		puts("Bob"); return 0;
	}
	if (find(A) != find(B)) {
		puts("Alice"); return 0;
	}
	dfs(A, 0);
	puts(col[A] == col[B] ? "Alice" :"Bob");
	return 0;
}
/*
不可能走出奇环,所以是二分图
*/

Details

Test #1:

score: 0
Runtime Error