QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#730744 | #7733. Cool, It’s Yesterday Four Times More | He2717970784 | WA | 3ms | 3792kb | C++17 | 1.8kb | 2024-11-09 21:22:11 | 2024-11-09 21:22:11 |
Judging History
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'