QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#113957 | #2213. Knight | yanran | WA | 63ms | 48596kb | C++14 | 1.5kb | 2023-06-20 11:10:41 | 2023-06-20 11:10:42 |
Judging History
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 * 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);
if (!r && !c) return puts("Bob"), 0;
for (int i = 1; i <= n * m; 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() == 0 || (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: 100
Accepted
time: 34ms
memory: 43832kb
Test #2:
score: 0
Accepted
time: 3ms
memory: 29044kb
Test #3:
score: 0
Accepted
time: 63ms
memory: 48596kb
Test #4:
score: -100
Wrong Answer
time: 47ms
memory: 37520kb