QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363881 | #8507. Clever Cell Choices | ucup-team2000# | WA | 0ms | 3720kb | C++20 | 1.9kb | 2024-03-24 04:49:28 | 2024-03-24 04:49:28 |
Judging History
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'