QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#269879#7733. Cool, It’s Yesterday Four Times MoreplutoWA 14ms4240kbC++204.5kb2023-11-30 09:35:562023-11-30 09:35:57

Judging History

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

  • [2023-11-30 09:35:57]
  • 评测
  • 测评结果：WA
  • 用时：14ms
  • 内存：4240kb
查看
  • [2023-11-30 09:35:56]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long

#define x first
#define y second

using namespace std;

using ll = long long;

struct Info {
    int x, y;
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<vector<vector<int>>>> f(n, vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int> (m))));
    vector<string> G(n);
    for (int i = 0; i < n; i++) {
        cin >> G[i];
    }
    vector<vector<pair<int, int>>> a(n, vector<pair<int, int>>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (G[i][j] == '.') {
                a[i][j] = {i, j};
            }
            else {
                a[i][j] = {-1, -1};
            }
        }
    }
    auto get = [&](vector<vector<Info>> t) -> void {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << i << " " << j << " now at : ";
                cout << t[i][j].x << " " << t[i][j].y << "\n";
            }
        }
        cout << "\n";
    };
    set<vector<vector<pair<int, int>>>> vis;
    auto dfs = [&](auto self, vector<vector<pair<int, int>>> g) -> void {
        if (vis.count(g)) return;
        vis.insert(g);
        vector<pair<int, int>> ok, fail;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j].x == -1) {
                    fail.push_back({i, j});
                }
                else {
                    ok.push_back({i, j});
                }
            }
        }
        for (auto [i, j] : ok) {
            for (auto [x, y] : fail) {
                f[i][j][x][y] = 1;
            }
        }
        if (ok.size() == 0) return;
        // get(g);
        auto na = g;
        // L
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j].x == -1) continue;
                if (g[i][j].y == 0) {
                    na[i][j].x = na[i][j].y = -1;
                }
                else if (G[g[i][j].x][g[i][j].y - 1] == 'O') {
                    na[i][j].x = na[i][j].y = -1;
                }
                else {
                    na[i][j].y--;
                }
            }
        }
        self(self, na);
        na = g;
        // R
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j].x == -1) continue;
                if (g[i][j].y == m - 1) {
                    na[i][j].x = na[i][j].y = -1;
                }
                else if (G[g[i][j].x][g[i][j].y + 1] == 'O') {
                    na[i][j].x = na[i][j].y = -1;
                }
                else {
                    na[i][j].y++;
                }
            }
        }
        self(self, na);
        na = g;
        // U
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j].x == -1) continue;
                if (g[i][j].x == 0) {
                    na[i][j].x = na[i][j].y = -1;
                }
                else if (G[g[i][j].x - 1][g[i][j].y] == 'O') {
                    na[i][j].x = na[i][j].y = -1;
                }
                else {
                    na[i][j].x--;
                }
            }
        }
        self(self, na);
        na = g;
        // R
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i][j].x == -1) continue;
                if (g[i][j].x == n - 1) {
                    na[i][j].x = na[i][j].y = -1;
                }
                else if (G[g[i][j].x + 1][g[i][j].y] == 'O') {
                    na[i][j].x = na[i][j].y = -1;
                }
                else {
                    na[i][j].x++;
                }
            }
        }
        self(self, na);
    };
    dfs(dfs, a);

    vector<vector<int>> v(n, vector<int>(m, 1));
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int x = 0; x < n; x++) {
                for (int y = 0; y < m; y++) {
                    if (i == x && y == j) f[i][j][x][y] = true;
                    v[i][j] &= f[i][j][x][y];
                }
            }
            res += v[i][j];
        }
    }
    cout << res << "\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3652kb

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: 14ms
memory: 4240kb

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
1
1
0
7
9
4
4
0
6
5
2
0
1
6
4
5
2
0
0
5
3
3
1
4
1
1
7
5
2
3
7
3
0
6
2
2
2
0
4
6
6
3
3
2
3
5
2
1
0
3
3
4
4
2
2
0
7
6
4
8
5
3
2
5
2
1
2
1
4
1
0
2
5
1
4
6
6
1
6
2
2
3
4
5
2
1
0
1
9
3
4
11
0
3
2
1
0
0
4
3
1
4
3
8
3
0
3
6
2
5
1
3
3
4
1
2
11
2
2
4
0
4
4
6
2
1
2
3
1
5
0
16
4
3
2
6
0
8
3
3
1...

result:

wrong answer 9th lines differ - expected: '0', found: '1'
English 繁體中文 简体中文

Server Time: 2024-12-12 06:58:11 | OpenSource Project