QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#590235 | #7733. Cool, It’s Yesterday Four Times More | shift | RE | 0ms | 0kb | C++20 | 3.4kb | 2024-09-25 22:46:05 | 2024-09-25 22:46:05 |
answer
#include <bits/stdc++.h>
using i64 = long long;
struct node {
int a, b, c, d;
};
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::string> g(n);
for(int i = 0; i < n; i ++ ) {
std::cin >> g[i];
}
std::vector<std::vector<std::vector<std::vector<int>>>> can;
std::vector<std::vector<std::vector<std::vector<std::array<int, 4>>>>> vis;
for(int i = 0; i < n; i ++ ) {
can.resize(n);
vis.resize(n);
for(int j = 0; j < m; j ++ ) {
can[i].resize(m);
vis[i].resize(m);
for(int u = 0; u < n; u ++ ) {
can[i][j].resize(n);
vis[i][j].resize(n);
for(int v = 0; v < m; v ++ ) {
can[i][j][u].resize(m);
vis[i][j][u].resize(m);
can[i][j][u][v] = 0;
vis[i][j][u][v] = {-1, -1, -1, -1};
}
}
}
}
static int dx[] = {0, 0, -1, 1};
static int dy[] = {-1, 1, 0, 0};
auto bfs = [&]() -> void {
auto ok = [&](int i, int j) -> bool {
return (i >= 0 and i < n and j >= 0 and j < m and g[i][j] == '.');
};
auto Go = [&](int sa, int sb, int sc, int sd) -> void {
std::queue<std::tuple<int, int, int, int>> q;
q.push({sa, sb, sc, sd});
vis[sa][sb][sc][sd] = {sa, sb, sc, sd};
while(not q.empty()) {
auto [a, b, c, d] = q.front(); q.pop();
for(int i = 0; i < 4; i ++ ) {
int ra = a + dx[i], rb = b + dy[i];
int rc = c + dx[i], rd = d + dy[i];
if(not ok(ra, rb)) continue;
if(not ok(rc, rd)) {
auto [i1, j1, i2, j2] = vis[a][b][c][d];
can[i1][j1][i2][j2] = true;
}
if(vis[ra][rb][rc][rd][0] != -1) continue;
q.push({ra, rb, rc, rd});
vis[ra][rb][rc][rd] = vis[a][b][c][d];
}
}
};
for(int i = 0; i < n; i ++ ) {
for(int j = 0; j < m; j ++ ) {
for(int u = 0; u < n; u ++ ) {
for(int v = 0; v < m; v ++ ) {
if(g[i][j] == '.' and g[u][v] == '.') {
if(vis[i][j][u][v][0] == -1) {
Go(i, j, u, v);
}
}
}
}
}
}
};
bfs();
int ans = 0;
for(int a = 0; a < n; a ++ ) {
for(int b = 0; b < m; b ++ ) {
if(g[a][b] != '.') continue;
int ok = true;
for(int c = 0; c < n; c ++ ) {
for(int d = 0; d < m; d ++ ) {
if((a != c or b != d) and g[a][b] == '.' and g[c][d] == '.') {
auto [i1, j1, i2, j2] = vis[a][b][c][d];
ok &= can[i1][j1][i2][j2];
}
}
}
ans += ok;
}
}
std::cout << ans << '\n';
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int T = 1;
std::cin >> T;
while(T -- ) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
4 2 5 .OO.. O..O. 1 3 O.O 1 3 .O. 2 3 OOO OOO