QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#590235#7733. Cool, It’s Yesterday Four Times MoreshiftRE 0ms0kbC++203.4kb2024-09-25 22:46:052024-09-25 22:46:05

Judging History

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

  • [2024-09-25 22:46:05]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: