QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#562473 | #8507. Clever Cell Choices | ucup-team3519# | WA | 0ms | 3844kb | C++20 | 1.9kb | 2024-09-13 17:50:52 | 2024-09-13 17:50:54 |
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);
}
}
}
}
for (auto &vec : adj) {
std::shuffle(vec.begin(), vec.end(), rng);
}
std::vector<uint8_t> vist(n * m);
std::vector<int> dep(n * m), dp(n * m);
auto dfs = [&](auto self, int node) -> int {
vist[node] = true;
int res = 0;
for (int to : adj[node]) {
if (vist[to]) {
if (dep[to] > dep[node]) {
res |= dp[to];
}
continue;
}
dep[to] = dep[node] + 1;
res |= self(self, to);
}
return dp[node] = !res;
};
int ans = 0;
for (int x = 0; x < n; ++x) {
for (int y = 0; y < m; ++y) {
if (map[x][y] == '#') {
continue;
}
std::fill(vist.begin(), vist.end(), false);
ans += dfs(dfs, get(x, y));
}
}
std::cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3844kb
input:
3 3 #.# ... #.#
output:
4
result:
ok 1 number(s): "4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
3 3 ..# ... ...
output:
0
result:
ok 1 number(s): "0"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 4 ...#
output:
2
result:
ok 1 number(s): "2"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
1 5 ####.
output:
1
result:
ok 1 number(s): "1"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1 6 #..###
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
2 5 ....# ###.#
output:
3
result:
ok 1 number(s): "3"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
2 6 ...##. .#.###
output:
4
result:
ok 1 number(s): "4"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
5 5 ##... ##.#. ##.## ##.#. .##..
output:
7
result:
ok 1 number(s): "7"
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3612kb
input:
6 6 ...##. #..#.. ...... ..#... #...## .#....
output:
4
result:
wrong answer 1st numbers differ - expected: '1', found: '4'