QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#730744#7733. Cool, It’s Yesterday Four Times MoreHe2717970784WA 3ms3792kbC++171.8kb2024-11-09 21:22:112024-11-09 21:22:11

Judging History

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

  • [2024-11-09 21:22:11]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3792kb
  • [2024-11-09 21:22:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
struct position{
    int x,y,id;
    bool operator < (const position it) const {
        return id < it.id;
    }
};
struct node{
    set<position>st;
    bool operator < (const node it) const {
        return st < it.st;
    }
};
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int solve(){
    int n = 0,m = 0;
    cin >> n >> m;
    vector<string>mp(n);
    for(int i = 0;i < n;i++){
        cin >> mp[i];
    }
    node start;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(mp[i][j] == '.'){
                position it;
                it.x = i;
                it.y = j;
                it.id = i * m + j;
                start.st.insert(it);
            }
        }
    }
    queue<node>q;
    q.push(start);
    map<node,bool>vis;
    vis[start] = true;
    set<int>ans;
    while(!q.empty()){
        node pre = q.front();
        q.pop();
        if((int)pre.st.size() == 1){
            ans.insert((*pre.st.begin()).id);
            continue;
        }
        for(int k = 0;k < 4;k++){
            node now;
            for(position it : pre.st){
                position temp = it;
                temp.x += dx[k];
                temp.y += dy[k];
                if(temp.x < 0 || temp.x >= n || temp.y < 0 || temp.y >= m || mp[temp.x][temp.y] == 'O'){
                    continue;
                }
                now.st.insert(temp);
            }
            if((!vis[now]) && (int)now.st.size()){
                vis[now] = true;
                q.push(now);
            }
        }
    }
    return (int)ans.size();
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t = 0;
    cin >> t;
    while(t--){
        int ans = solve();
        cout << ans << endl;
    }
    return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3ms
memory: 3792kb

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
5
9
4
4
0
6
2
2
0
1
6
4
5
2
0
0
5
3
3
1
2
1
0
5
2
2
2
7
2
0
4
2
2
2
0
4
6
5
3
3
2
3
4
2
1
0
3
3
4
4
2
2
0
7
5
2
8
5
3
2
5
2
1
2
1
2
0
0
2
5
1
4
4
6
1
6
2
2
2
4
5
2
1
0
1
8
3
4
11
0
2
2
1
0
0
2
2
1
4
2
7
3
0
3
5
2
4
1
2
3
2
0
2
11
2
2
4
0
2
4
4
2
1
2
2
0
5
0
16
4
3
2
5
0
8
2
3
1...

result:

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