QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#588486 | #7733. Cool, It’s Yesterday Four Times More | argtarg | RE | 0ms | 3816kb | C++20 | 2.6kb | 2024-09-25 12:02:53 | 2024-09-25 12:02:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T; cin >> T;
while (T--)solve();
return 0;
}
int oo = 0;
void solve() {
int n, m;
cin >> n >> m;
vector<string>s(n);
vector<bool>v(n * m);
auto get = [&](int x, int y)->int {
return x * m + y;
};
for (int i = 0; i < n; i++) {
cin >> s[i];
for (int j = 0; j < m; j++) {
if (s[i][j] == '.')v[get(i, j)] = 0;
else v[get(i, j)] = 1;
}
}
vector<int>p(n * m), vis(n * m), sz(n * m);
vector<int>dx = { 0,0,-1,1 };
vector<int>dy = { -1,1,0,0 };
auto dfs1 = [&](auto dfs1, int u, int f)->void {
int x = u / m, y = u % m;
sz[f]++;
p[u] = f;
for (int k = 0; k < 4; k++) {
int nx = dx[k] + x, ny = dy[k] + y;
int tt = get(nx, ny);
if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[tt] == 1 || v[tt] == 1)continue;
vis[tt] = 1;
dfs1(dfs1, tt, f);
}
};
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int t = get(i, j);
if (v[t] == 1 || vis[t] == 1)continue;
vis[t] = 1;
dfs1(dfs1, t, t);
}
}
/*if (n == 6 && m == 160||oo==1) {
oo = 1;
cout << -1 << endl;
return;
}*/
auto fail = [&](int x, int y)->bool {
if (x < 0 || y < 0 || x >= n || y >= m || v[get(x, y)] == 1)return 1;
return 0;
};
int ok = 0;
int cnt = 0;
vector<int>add(n + 1);
auto dfs = [&](auto dfs, int u, int d)->void {
if (ok == 1)return;
int i = u / m, j = u % m, x = d / m, y = d % m;
for (int k = 0; k < 4; k++) {
int ni = dx[k] + i, nj = dy[k] + j, nx = dx[k] + x, ny = dy[k] + y;
if (fail(ni, nj))continue;
if (fail(nx, ny)) {
ok = 1;
return;
}
int nu = get(ni, nj), nd = get(nx, ny);
if (vis[nu] == 1 || vis[nd] == 1)continue;
vis[nu] = vis[nd] = 1;
dfs(dfs, nu, nd);
add[++cnt] = nu;
add[++cnt] = nd;
//vis[nu] = vis[nd] = 0;
}
};
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int u = get(i, j);
if (p[u] != u)continue;
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
vis[get(x, y)] = 0;
}
}
int ook = 1;
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
int t = get(x, y);
if (p[t] == u || v[t] == 1)continue;
ok = 0;
vis[u] = vis[t] = 1;
dfs(dfs, u, t);
vis[u] = vis[t] = 0;
for (int i = 1; i <= cnt; i++) {
vis[add[i]] = 0;
}
cnt = 0;
ook = min(ook, ok);
}
}
ans += (ook == 1 ? sz[u] : 0);
}
}
cout << ans << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3816kb
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
Runtime Error
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. ...