QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#707767#7733. Cool, It’s Yesterday Four Times MoreQSteve_PaulWA 1ms3764kbC++233.4kb2024-11-03 17:27:072024-11-03 17:27:08

Judging History

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

  • [2024-11-03 17:27:08]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3764kb
  • [2024-11-03 17:27:07]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

int n, m;

void dfs(int x, int y, int val, vector<string > &s, vector<vector<int> > &a, vector<vector<int> > &b, vector<int> &num) {
    a[x][y] = val;
    if (b[x][y] )  return;
    num[val] ++;  b[x][y] = 1;
    if (x - 1 > 0 && s[x-1][y] == '.')  dfs(x - 1, y, val, s, a, b, num);
    if (x + 1 <= n && s[x+1][y] == '.') dfs(x + 1, y, val, s, a, b, num);
    if (y - 1 > 0 && s[x][y-1] == '.')  dfs(x, y - 1, val, s, a, b, num);
    if (y + 1 <= n && s[x][y+1] == '.') dfs(x, y + 1, val, s, a, b, num);
}
bool fun(int x, int y, vector<string> &s) {
    if (x <= 0 || x > n || y <= 0 || y > m) return false;
    if (s[x][y] == '.')  return true;
    return false;
}
void work() {
    cin >> n >> m;
    vector<string> s(n+10);
    for (int i=1; i<=n; i++) {
        cin >> s[i];
        s[i] = " " + s[i];
    }
    vector<vector<int> > a(n+10, vector<int>(m+10, 0)), b(n+10, vector<int>(m+10, 0));
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            if (s[i][j] == '.') {
                a[i][j] = i * m + j;
            }
        }
    }
    vector<array<int, 2> > id;
    vector<int> num((n + 10) * (m + 10) + 10, 0);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            if (!a[i][j] )  continue;
            if (!b[i][j]) {
                id.push_back({i, j});
                dfs(i, j, i * m + j, s, a, b, num);
            }
        }
    }
    int ans = 0;
    for (int i=0; i<id.size(); i++) {
        vector<int> bo(id.size() + 10, 0);
        for (int j=0; j<id.size(); j++) {
            if (i == j) {
                bo[j] = 1;  continue;
            }
            if (num[id[j][0] * m + id[j][1]] < num[id[i][0] * m + id[j][1]]) {
                bo[j] = 1;  continue;
            }
        }
        map<array<int, 2> , int> mp;
        queue<array<int, 2> > qu;
        qu.push({0, 0});  mp[{0, 0}] = 1;
        while (!qu.empty()) {
            auto [dx, dy] = qu.front();  qu.pop();
            for (int j=0; j<id.size(); j++) {
                if (bo[j] )  continue;
                if (!fun(id[j][0]+dx, id[j][1]+dy, s) ) {
                    bo[j] = 1;
                }
            }
            int fx = id[i][0] + dx, fy = id[i][1] + dy;
            if (fun(fx + 1, fy, s) && !mp[{dx + 1, dy}]) {
                qu.push({dx + 1, dy});  mp[{dx + 1, dy}] = 1;
            }
            if (fun(fx - 1, fy, s) && !mp[{dx - 1, dy}]) {
                qu.push({dx - 1, dy});  mp[{dx - 1, dy}] = 1;
            }
            if (fun(fx, fy + 1, s) && !mp[{dx, dy + 1}]) {
                qu.push({dx, dy + 1});  mp[{dx, dy + 1}] = 1;
            }
            if (fun(fx, fy - 1, s) && !mp[{dx, dy - 1}]) {
                qu.push({dx, dy - 1});  mp[{dx, dy - 1}] = 1;
            }
        }
        bool fbo = true;
        for (int j=0; j<id.size(); j++) {
            if (bo[j] )  continue;
            fbo = false;  break;
        }
        if (fbo) {
            ans += num[id[i][0] * m + id[i][1]];
        }
    }
    cout << ans << '\n';
}
int main()
{
    #ifdef QHK
    freopen("qi.in","r",stdin);
    freopen("qi.out","w",stdout);
    #endif
    ios::sync_with_stdio(false); cin.tie(0); 
    int T=1;
    cin >> T;
    while(T--){
        work();
    }

   return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

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
3
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
3
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 39th lines differ - expected: '7', found: '9'