QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#363881#8507. Clever Cell Choicesucup-team2000#WA 0ms3720kbC++201.9kb2024-03-24 04:49:282024-03-24 04:49:28

Judging History

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

  • [2024-03-24 04:49:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3720kb
  • [2024-03-24 04:49:28]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define f first
#define s second
#define lep(i,a,b) for (int i=(a); i <= (b); i++)
#define rep(i,b,a) for (int i = (b); i >= (a); i--)

char S[55][55]; int N, M;
map<pi, vector<pi>> adj;
map<int, vector<pi>> conn; map<pi, bool> vis;
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1}; 

bool isValid(int i, int j) {
    return i >= 1 && j >= 1 && i <= N && j <= M && S[i][j] == '.';
}

void dfs(pi nn, int col) {
    vis[nn] = true;
    conn[col].push_back(nn);
    for (auto cc : adj[nn]) {
        if (!vis[cc]) 
            dfs(cc, col);
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j) cin >> S[i][j];
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (S[i][j] == '.') {
                for (int x = 0; x < 4; ++x) {
                        int xx = i + dx[x];
                        int yy = j + dy[x];
                        if (isValid(xx, yy)) {
                            adj[{i, j}].push_back({xx, yy});
                    }
                }
            }
        }
    }
    int k = 0;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            if (isValid(i, j) && !vis[{i, j}]) {
                dfs({i, j}, k);
                k++;
            }
        }
    }
    int ans = 0;
    for (auto pp : conn) {
        // cerr << pp.f << ":\n";
        int cnt0 = 0, cnt1 = 0;
        for (auto nn : pp.s) {
            // cerr << nn.f << " " << nn.s << endl;
            cnt0 += (nn.f + nn.s)&1;
            cnt1 += !((nn.f + nn.s)&1);
        }
        if (cnt0 == cnt1) continue;
        else ans += max(cnt0, cnt1);
    }
    cout << ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3 3
#.#
...
#.#

output:

4

result:

ok 1 number(s): "4"

Test #2:

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

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

input:

1 5
####.

output:

1

result:

ok 1 number(s): "1"

Test #5:

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

input:

1 6
#..###

output:

0

result:

ok 1 number(s): "0"

Test #6:

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

input:

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

output:

3

result:

ok 1 number(s): "3"

Test #7:

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

input:

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

output:

4

result:

ok 1 number(s): "4"

Test #8:

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

input:

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

output:

7

result:

ok 1 number(s): "7"

Test #9:

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

input:

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

output:

1

result:

ok 1 number(s): "1"

Test #10:

score: -100
Wrong Answer
time: 0ms
memory: 3720kb

input:

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

output:

29

result:

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