QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#49880#3832. Robert Floydckiseki#AC ✓45ms13168kbC++202.7kb2022-09-23 19:26:452022-09-23 19:26:46

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-23 19:26:46]
  • 评测
  • 测评结果:AC
  • 用时:45ms
  • 内存:13168kb
  • [2022-09-23 19:26:45]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2077;

bool V[maxn][maxn], H[maxn][maxn];
bool vis[maxn][maxn];

bool ok(int i, int j) {
    return i >= 0 && i < maxn && j >= 0 && j < maxn;
}

void bfs(int ii, int jj) {
    queue<pair<int, int>> q;
    vis[ii][jj] = true;
    q.emplace(ii, jj);
    auto dfs = [&](int i, int j) {
        vis[i][j] = true;
        q.emplace(i, j);
    };
    while (not q.empty()) {
        auto [i, j] = q.front(); q.pop();
        if (ok(i-1,j) && not vis[i-1][j] && not H[i][j])
            dfs(i-1, j);
        if (ok(i+1,j) && not vis[i+1][j] && not H[i+1][j])
            dfs(i+1, j);
        if (ok(i,j-1) && not vis[i][j-1] && not V[i][j])
            dfs(i, j-1);
        if (ok(i,j+1) && not vis[i][j+1] && not V[i][j+1])
            dfs(i, j+1);
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    for (int i = 0; i < maxn; i++)
        for (int j = 0; j < maxn; j++)
            vis[i][j] = false;

    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int x = 0, y = 0;
        int mnx = 1e9, mxx = -1e9;
        int mny = 1e9, mxy = -1e9;
        vector<pair<int,int>> ver, hor, v;
        for (char c: s) {
            if (c == 'L') {
                x -= 1;
                ver.emplace_back(x, y); // (x,y-1) (x,y)
            } else if (c == 'R') {
                ver.emplace_back(x, y); // (x,y-1) (x,y)
                x += 1;
            } else if (c == 'U') {
                hor.emplace_back(x, y); // (x-1,y) (x,y)
                y += 1;
            } else if (c == 'D') {
                y -= 1;
                hor.emplace_back(x, y); // (x-1,y) (x,y)
            }
            mnx = min(mnx, x);
            mxx = max(mxx, x);
            mny = min(mny, y);
            mxy = max(mxy, y);
            v.emplace_back(x, y);
            v.emplace_back(x-1, y);
            v.emplace_back(x, y-1);
            v.emplace_back(x-1, y-1);
        }

        --mnx, --mny;
        --mnx, --mny;
        ++mxx, ++mxy;
        ++mxx, ++mxy;

        for (auto &[a, b]: ver) {
            a -= mnx;
            b -= mny;
        }
        for (auto &[a, b]: hor) {
            a -= mnx;
            b -= mny;
        }
        for (auto &[a, b]: v) {
            a -= mnx;
            b -= mny;
        }

        for (auto &[a, b]: ver) V[a][b] = true;
        for (auto &[a, b]: hor) H[a][b] = true;

        for (auto [i, j]: v)
            vis[i][j] = false;

        int cnt = 0;
        for (auto [i, j]: v) {
            if (!vis[i][j]) {
                bfs(i, j);
                ++cnt;
            }
        }
        cout << cnt << '\n';

        for (auto &[a, b]: ver) V[a][b] = false;
        for (auto &[a, b]: hor) H[a][b] = false;
    }
    return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 45ms
memory: 13168kb

input:

30
URDR
URDRDLDR
URDRDLDRDLULDLDR
URDRDLDRDLULDLDRDLULURULDLULDLDR
URDRDLDRDLULDLDRDLULURULDLULDLDRDLULURULURDRURULDLULURULDLULDLDR
URDRDLDRDLULDLDRDLULURULDLULDLDRDLULURULURDRURULDLULURULDLULDLDRDLULURULURDRURULURDRDLDRURDRURULDLULURULURDRURULDLULURULDLULDLDR
URDRDLDRDLULDLDRDLULURULDLULDLDRDLULURU...

output:

1
1
2
5
12
29
68
153
336
725
331
235
333
213
357
249
322
229
342
230
348
231
328
225
366
513
2
2
2
3

result:

ok 30 lines