QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562644#8507. Clever Cell Choicesucup-team3519#WA 0ms3800kbC++202.6kb2024-09-13 19:44:532024-09-13 19:44:54

Judging History

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

  • [2024-09-13 19:44:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3800kb
  • [2024-09-13 19:44:53]
  • 提交

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

    randomize();

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3
#.#
...
#.#

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

input:

3 3
..#
...
...

output:

0

result:

ok 1 number(s): "0"

Test #3:

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

input:

1 4
...#

output:

2

result:

ok 1 number(s): "2"

Test #4:

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

input:

1 5
####.

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

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: 3588kb

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: -100
Wrong Answer
time: 0ms
memory: 3600kb

input:

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

output:

5

result:

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