QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#606789#7733. Cool, It’s Yesterday Four Times MorelongyinWA 1ms3852kbC++201.9kb2024-10-03 12:13:292024-10-03 12:13:30

Judging History

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

  • [2024-10-03 12:13:30]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3852kb
  • [2024-10-03 12:13:29]
  • 提交

answer

#include <bits/stdc++.h>
//#define int long long
#define endl "\n"
using namespace std;

using ll = long long;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0}; 

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> grid(n);
    for (auto& s : grid) {
        cin >> s;
    }

    auto invalid = [&](int x, int y) -> bool {
        return x < 0 || x >= n || y < 0 || y >= m;
    };

    auto bfs = [&](int ex, int ey) -> set<pair<int, int>> {
        set<pair<int, int>> cor;
        queue<pair<int, int>> q;
        q.emplace(ex, ey);
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            cor.emplace(x - ex, y - ey);
            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if (invalid(xx, yy) || grid[xx][yy] != '.')
                    continue;
                q.emplace(xx, yy);
                grid[xx][yy] = '*';
            }
        }
        return cor;
    };

    vector<set<pair<int, int>>> space;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '.')
                space.emplace_back(bfs(i, j));
        }
    }

    int ans = 0;
    for (int i = 0; i < space.size(); i++) {
        bool flag = true;
        for (int j = 0; j < space.size(); j++) {
            if (i == j)
                continue;
            int cnt = space[i].size();
            for (auto d : space[i]) {
                if (space[j].count(d)) {
                    cnt--;
                }
            }
            if (!cnt) {
                flag = false;
                break;
            }
        }
        ans += flag ? space[i].size() : 0;
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int T = 1;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4
2 5
.OO..
O..O.
1 3
O.O
1 3
.O.
2 3
OOO
OOO

output:

3
1
0
0

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3852kb

input:

200
2 4
OOO.
OO..
2 3
OOO
.O.
3 3
O.O
OOO
OO.
4 1
.
.
O
O
1 2
.O
1 1
.
2 5
.OO..
.O.O.
2 1
O
O
1 1
O
1 3
.OO
5 1
O
O
.
O
.
5 2
O.
..
O.
.O
..
5 3
...
...
.OO
..O
OOO
3 5
..O.O
.O.O.
.OO.O
5 2
.O
OO
O.
O.
..
2 1
O
O
3 5
.O.OO
O...O
..OO.
1 5
.....
5 1
O
.
O
.
.
5 3
OOO
OO.
.OO
OO.
O.O
2 1
O
.
5 2
O.
...

output:

3
0
0
2
1
1
5
0
0
1
0
7
9
4
4
0
6
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
0
7
5
2
3
9
3
0
6
2
2
2
0
4
6
6
3
5
2
5
5
2
1
0
3
3
4
4
2
2
0
7
6
4
8
5
3
2
5
2
1
2
1
4
0
0
2
5
1
4
6
9
1
6
2
2
5
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
10
3
0
3
6
2
5
1
3
3
4
0
2
11
2
2
4
0
4
4
6
2
1
2
3
0
5
0
16
4
3
2
6
0
8
3
3
...

result:

wrong answer 7th lines differ - expected: '3', found: '5'