QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#562646 | #8507. Clever Cell Choices | ucup-team3519# | WA | 0ms | 3796kb | C++20 | 2.6kb | 2024-09-13 19:45:17 | 2024-09-13 19:45:18 |
Judging History
answer
#include <bits/stdc++.h>
constexpr int D = 4;
constexpr int DX[]{1, -1, 0, 0};
constexpr int DY[]{0, 0, 1, -1};
std::mt19937 rng(std::random_device{}());
int main() {
int n, m;
std::cin >> n >> m;
std::vector<std::string> map(n);
for (int i = 0; i < n; ++i) {
std::cin >> map[i];
}
auto get = [&](int x, int y) -> int {
return x * m + y;
};
std::vector<std::vector<int>> adj(n * m);
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
if (map[x][y] == '#') {
continue;
}
for (int d = 0; d < D; ++d) {
int nx = x + DX[d], ny = y + DY[d];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] != '#') {
int u = get(x, y), v = get(nx, ny);
adj[u].push_back(v);
adj[v].push_back(u);
}
}
}
}
auto randomize = [&]() {
for (auto &vec : adj) {
std::shuffle(vec.begin(), vec.end(), rng);
}
};
auto check = [&](int root) -> int {
std::vector<int> st;
st.push_back(root);
std::vector<uint8_t> vist(n * m);
vist[root] = true;
auto hasadj = [&](int x) {
for (int to : adj[x]) {
if (!vist[to]) {
return true;
}
}
return false;
};
bool win = true;
while (true) {
while (hasadj(st.back())) {
int next = -1;
for (int to : adj[st.back()]) {
if (!vist[to]) {
next = to;
break;
}
}
assert(next != -1);
st.push_back(next);
vist[next] = true;
}
win = st.size() & 1;
while (st.size() > 2) {
st.pop_back();
st.pop_back();
if (!st.empty() && hasadj(st.back())) {
break;
}
}
if (st.empty() || !hasadj(st.back())) {
break;
}
}
return win;
};
int ans = 0;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
if (map[x][y] == '#') {
continue;
}
ans += check(get(x, y));
}
}
std::cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3792kb
input:
3 3 #.# ... #.#
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
3 3 ..# ... ...
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
1 4 ...#
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
1 5 ####.
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1 6 #..###
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
2 5 ....# ###.#
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
2 6 ...##. .#.###
output:
4
result:
ok 1 number(s): "4"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
5 5 ##... ##.#. ##.## ##.#. .##..
output:
7
result:
ok 1 number(s): "7"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
6 6 ...##. #..#.. ...... ..#... #...## .#....
output:
1
result:
ok 1 number(s): "1"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
10 10 ####.#...# .#.###.... #....#..#. .....#.#.. ##.#..#.#. ..#..##... .##.#####. #######.## .#.#.##..# .#.###.##.
output:
26
result:
ok 1 number(s): "26"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
10 10 ..#..#.### .#######.# .#.####.#. ......#### #..#..#.#. ...#.###.# #.#...#.#. .#...#.... ...#.#.#.# ...###....
output:
21
result:
ok 1 number(s): "21"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
15 15 #......#.#.###. #.##...####..#. ##.....##.##.#. #.###.#..#...## ....###.##.#.#. .#..#.###.##.#. ######.#.####.# .#....#..####.. .....#.###.##.. #..##.###.##### #.##.#####..### .#######..##.#. ##....#.##...#. ....#####.##.## ...#.#........#
output:
51
result:
ok 1 number(s): "51"
Test #13:
score: -100
Wrong Answer
time: 0ms
memory: 3608kb
input:
15 15 ###.#......#... #.....#.#.###.# #..#.#.###..#.. .#####.##.#..#. ...#.##.#..#.#. #.#.###.....### ......#..##.... ..##..#.#.#...# ..#..#..#...... ....####...#..# .####..#.#.##.# ###.#..#.#.#... .#.##.##....##. .#.#####.#..#.# #.#.#.##.#.....
output:
62
result:
wrong answer 1st numbers differ - expected: '61', found: '62'