QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562546#8507. Clever Cell Choicesucup-team3519#WA 9ms3856kbC++202.0kb2024-09-13 18:28:212024-09-13 18:28:24

Judging History

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

  • [2024-09-13 18:28:24]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:3856kb
  • [2024-09-13 18:28:21]
  • 提交

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);
        }
    };

    std::vector<uint8_t> vist(n * m);
    auto dfs = [&](auto self, int node) -> int {
        vist[node] = true;

        int res = 0;
        for (int to : adj[node]) {
            if (vist[to]) {
                continue;
            }
            res |= self(self, to);
        }
        return !res;
    };

    int ans = 0;
    for (int x = 0; x < n; ++x) {
        for (int y = 0; y < m; ++y) {
            if (map[x][y] == '#') {
                continue;
            }
            bool flag = true;
            for (int _ = 0; _ < 500; ++_) {
                randomize();
                std::fill(vist.begin(), vist.end(), false);
                if (!dfs(dfs, get(x, y))) {
                    flag = false;
                    break;
                }
            }
            ans += flag;
        }
    }

    std::cout << ans << '\n';
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3856kb

input:

3 3
#.#
...
#.#

output:

4

result:

ok 1 number(s): "4"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

3 3
..#
...
...

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

1 4
...#

output:

2

result:

ok 1 number(s): "2"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3516kb

input:

1 5
####.

output:

1

result:

ok 1 number(s): "1"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

1 6
#..###

output:

0

result:

ok 1 number(s): "0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

2 5
....#
###.#

output:

3

result:

ok 1 number(s): "3"

Test #7:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

2 6
...##.
.#.###

output:

4

result:

ok 1 number(s): "4"

Test #8:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

5 5
##...
##.#.
##.##
##.#.
.##..

output:

7

result:

ok 1 number(s): "7"

Test #9:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

6 6
...##.
#..#..
......
..#...
#...##
.#....

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: -100
Wrong Answer
time: 9ms
memory: 3620kb

input:

10 10
####.#...#
.#.###....
#....#..#.
.....#.#..
##.#..#.#.
..#..##...
.##.#####.
#######.##
.#.#.##..#
.#.###.##.

output:

21

result:

wrong answer 1st numbers differ - expected: '26', found: '21'