QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#722202#7751. Palindrome Pathucup-team5217WA 898ms17064kbC++235.3kb2024-11-07 18:10:032024-11-07 18:10:04

Judging History

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

  • [2024-11-07 18:10:04]
  • 评测
  • 测评结果:WA
  • 用时:898ms
  • 内存:17064kb
  • [2024-11-07 18:10:03]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'

#define maxn 35
#define maxv 810005

typedef pair<int, int> pii;

const int way[4][2] = {{0, -1}, {0, +1}, {-1, 0}, {+1, 0}};

string a[maxn];
pii nxt[maxv];
int dis[maxv];
bool vis[maxn][maxn];
vector<pii> graph[maxv], rgraph[maxv];

int _(pii x, pii y) { return (x.first - 1) * 27000 + (x.second - 1) * 900 + (y.first - 1) * 30 + (y.second - 1);  }
pair<pii, pii> $(int v) { return {{v / 27000 + 1, v / 900 % 30 + 1}, {v / 30 % 30 + 1, v % 30 + 1}}; }

void solve(void) {
    int n, m;
    cin >> n >> m;

    a[0] = a[n + 1] = string(m + 2, '0');
    for (int i = 1; i <= n; i++) cin >> a[i], a[i] = '0' + a[i] + '0';

    auto addEdge = [&](int p, int q, int t) {
        return graph[p].emplace_back(q, t), rgraph[q].emplace_back(p, t);
    };

    for (int ax = 1; ax <= n; ax++)
        for (int ay = 1; ay <= m; ay++)
            for (int bx = 1; bx <= n; bx++)
                for (int by = 1; by <= m; by++)
                    if (a[ax][ay] == '1' && a[bx][by] == '1')
                        for (int t = 0; t < 4; t++) {
                            int tax = ax + way[t][0], tay = ay + way[t][1];
                            if (a[tax][tay] == '0') tax = ax, tay = ay;
                            int tbx = bx - way[t][0], tby = by - way[t][1];
                            if (a[tbx][tby] == '1') addEdge(_({ax, ay}, {bx, by}), _({tax, tay}, {tbx, tby}), t);
                            if (a[bx + way[t][0]][by + way[t][1]] == '0')
                                addEdge(_({ax, ay}, {bx, by}), _({tax, tay}, {bx, by}), t);
                        }

    for (int i = 0; i < maxv; i++) nxt[i] = {-1, -1}, dis[i] = -1;
    queue<int> que;
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= m; y++)
            if (a[x][y] == '1')
                nxt[_({x, y}, {x, y})] = {0, 4}, dis[_({x, y}, {x, y})] = 0, que.push(_({x, y}, {x, y}));
    while (!que.empty()) {
        int p = que.front();
        que.pop();
        for (auto [q, t] : rgraph[p])
            if (dis[q] == -1) nxt[q] = {p, t}, dis[q] = dis[p] + 1, que.push(q);
    }

    // for (int ax = 1; ax <= n; ax++)
    //     for (int ay = 1; ay <= m; ay++)
    //         for (int bx = 1; bx <= n; bx++)
    //             for (int by = 1; by <= m; by++) {
    //                 int p = _({ax, ay}, {bx, by});
    //                 cerr << "# " << ax << ' ' << ay << ' ' << bx << ' ' << by << ' ' << dis[p] << endl;
    //                 // auto [q, t] = nxt[_({ax,  ay}, {bx, by})];
    //                 for (auto [q, t] : graph[p]) {
    //                     auto [u, v] = $(q);
    //                     cerr << u.first << ' ' << u.second << ' ' << v.first << ' ' << v.second << ' ' << t << endl;
    //                 }
    //             }

    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    if (dis[_({sx, sy}, {tx, ty})] == -1) return cout << -1 << endl, void();
    mt19937 rnd(114514);
    while (clock() * 1000. / CLOCKS_PER_SEC < 900) {
        int rest = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (a[i][j] == '1') vis[i][j] = true, rest++;

        int p = _({sx, sy}, {tx, ty});
        string ans;
        vis[sx][sy] = vis[tx][ty] = false, rest -= 2;

        while (rest) {
            bool mov = false;
            shuffle(graph[p].begin(), graph[p].end(), rnd);
            for (auto [q, t] : graph[p])
                if (dis[q] != -1 && (int)ans.size() + 1 + dis[q] <= int(1e6)) {
                    p = q, mov = true, ans.push_back("LRUD"[t]);
                    auto [u, v] = $(p);
                    rest -= vis[u.first][u.second], vis[u.first][u.second] = false;
                    rest -= vis[v.first][v.second], vis[v.first][v.second] = false;
                    // cerr << "! " << u.first << ' ' << u.second << ' ' << v.first << ' ' << v.second << ' ' << rest << endl;
                    // cerr << ans << endl;
                    break;
                }
            if (!mov) break;
        }
        if (rest) continue;
        while (dis[p]) ans.push_back("LRUD"[nxt[p].second]), p = nxt[p].first;
        string nans = ans;
        reverse(ans.begin(), ans.end());
        nans.append(ans.begin(), ans.end());
        cout << nans << endl;

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) vis[i][j] = true;

        int x = 1, y = 1;
        vis[x][y] = false;
        for (auto i : nans) {
            int t;
            if (i == 'L')
                t = 0;
            else if (i == 'R')
                t = 1;
            else if (i == 'U')
                t = 2;
            else
                t = 3;
            int tx = x + way[t][0], ty = y + way[t][1];
            if (a[tx][ty] == '0') tx = x, ty = y;
            x = tx, y = ty;
            vis[x][y] = false;
        }
        assert(x == tx && y == ty);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (a[i][j] == '1') assert(!vis[i][j]);
        return;
    }
    cout << -1 << endl;
    return;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int _ = 1;
    while (_--) solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 14772kb

input:

2 2
11
11
1 1 2 2

output:

RLDDLR

result:

ok Valid Solution (Length = 6).

Test #2:

score: 0
Accepted
time: 4ms
memory: 13720kb

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: -100
Wrong Answer
time: 898ms
memory: 17064kb

input:

1 1
1
1 1 1 1

output:

-1

result:

wrong answer Solution Exists, But -1 Found.