QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#657813 | #7733. Cool, It’s Yesterday Four Times More | AkTtt | WA | 1ms | 3576kb | C++14 | 2.5kb | 2024-10-19 15:31:06 | 2024-10-19 15:31:07 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <queue>
using namespace std;
#define endl '\n'
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 10;
const LL INFF = 0x3f3f3f3f3f3f3f3f;
const int INF = 0x3f3f3f3f,mod = 998244353;
#define debug(x) cout<< "[debug]" #x << " = " << x <<endl
int n, m;
int dx[5] = {1, -1, 0, 0};
int dy[5] = {0, 0, 1, -1};
void solve()
{
cin >> n >> m;
vector<vector<char>> c(n + 1, vector<char>(m + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
cin >> c[i][j];
}
}
int ans = 0;
vector<vector<int>> st(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(!st[i][j] && c[i][j] == '.'){
queue<PII> q1, q2;
vector<vector<int>> sw(n + 1, vector<int>(m + 1));
q1.push({i, j});
sw[i][j] = 1;
int cnt = 1;
while(q1.size()){
auto [x, y] = q1.front();
q1.pop();
for(int i = 0; i < 4; i++){
int tx = x + dx[i];
int ty = y + dy[i];
if(tx < 1 || tx > n || ty < 1 || ty > m)continue;
if(!sw[tx][ty] && c[tx][ty] == '.'){
sw[tx][ty] = 1;
q1.push({tx, ty});
cnt++;
}
}
}
q1.push({i, j});
for(int k = 1; k <= n; k++){
for(int l = 1; l <= m; l++){
if(c[k][l] == '.' && !sw[k][l])q2.push({k, l});
}
}
while(q1.size()){
auto [x, y] = q1.front();
q1.pop();
for(int i = 0; i < 4; i++){
int tx = x + dx[i];
int ty = y + dy[i];
if(tx < 1 || tx > n || ty < 1 || ty > m)continue;
if(!st[tx][ty] && c[tx][ty] == '.'){
st[tx][ty] = 1;
q1.push({tx, ty});
queue<PII> q3;
while(q2.size()){
auto [x, y] = q2.front();
q2.pop();
int tx = x + dx[i];
int ty = y + dy[i];
if(tx < 1 || tx > n || ty < 1 || ty > m)continue;
if(c[tx][ty] == '.')q3.push({tx, ty});
}
q2 = q3;
break;
}
}
}
if(!q2.size())ans += cnt;
}
}
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
cin >> T;
while(T--)
{
solve();
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3576kb
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: 3576kb
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:
6 0 0 2 1 1 3 0 0 1 0 4 18 8 4 0 12 5 2 0 1 12 4 5 2 0 0 5 3 3 1 4 1 0 4 5 2 3 14 3 0 6 2 2 2 0 8 12 18 0 3 2 3 5 2 1 0 3 6 4 8 2 2 0 7 12 4 8 10 3 2 5 2 1 2 1 4 0 0 2 10 1 4 6 12 1 12 2 2 3 4 10 2 1 0 1 9 3 4 11 0 3 2 1 0 0 4 3 1 8 3 16 3 0 3 6 2 5 1 3 3 4 0 2 22 2 2 4 0 4 4 6 2 1 2 3 0 5 0 48 0 3 ...
result:
wrong answer 1st lines differ - expected: '3', found: '6'