QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#562473#8507. Clever Cell Choicesucup-team3519#WA 0ms3844kbC++201.9kb2024-09-13 17:50:522024-09-13 17:50:54

Judging History

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

  • [2024-09-13 17:50:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3844kb
  • [2024-09-13 17:50:52]
  • 提交

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'