QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404917#7751. Palindrome PathSorting#WA 8ms28108kbC++205.8kb2024-05-05 00:25:342024-05-05 00:25:35

Judging History

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

  • [2024-05-05 00:25:35]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:28108kb
  • [2024-05-05 00:25:34]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using pii = pair<int, int>;
using ll = long long;
using vpii = vector<pii>;

using ppiii = pair<pii, int>;

using vb = vector<bool>;
using vvb = vector<vb>;

vi par;

pii operator+(pii a, pii b) {
    return {a.first + b.first, a.second + b.second};
}

pii operator-(pii a, pii b) {
    return {a.first - b.first, a.second - b.second};
}

pii moves[4] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
char ops[4] = {'U', 'D', 'R', 'L'};

void dfs(pii u, vvb &vis, vvb &grid, vi &seq) {
    int x, y;
    tie(x, y) = u;
    vis[x][y] = 1;
    for(int d = 0; d < 4; d++) {
        pii v = u + moves[d];
        if(vis[v.first][v.second]) continue;
        if(!grid[v.first][v.second]) continue;
        seq.push_back(d);
        dfs(v, vis, grid, seq);
        seq.push_back(d^1);
    }
}

pii follow(pii u, vi seq, vvb &grid, bool rev) {
    if(rev) {
        reverse(seq.begin(), seq.end());
    }
    for(int op : seq) {
        pii v;
        // if(!rev) {
             v = u + moves[op];
        // } else {
        //     v = u - moves[op];
        // }
        if(!grid[v.first][v.second]) continue;
        u = v;
    }
    return u;
}

const int N = 33;
bool vis[N][N][N][N];
int parop[N][N][N][N];
pair<pii, pii> parnode[N][N][N][N];

void find_path(vvb &grid, pii start2, pii end2) {
    memset(vis, 0, sizeof(vis));
    memset(parop, 0, sizeof(parop));
    memset(parnode, 0, sizeof(parnode));
    queue<pair<pii, pii>> q;
    q.push({start2, end2});
    parop[start2.first][start2.second][end2.first][end2.second] = -1;
    vis[start2.first][start2.second][end2.first][end2.second] = 1;
    while(!q.empty()) {
        pii s, e;
        tie(s, e) = q.front();
        q.pop();
        for(int d = 0; d < 4; d++) {
            pii s1 = s + moves[d];
            if(!grid[s1.first][s1.second]) {
                s1 = s;
            }
            for(int emove = 0; emove <= 1; emove++) {
                pii e1 = e;
                if(emove) {
                    e1 = e - moves[d];
                } else {
                    pii nxt = e + moves[d];
                    if(grid[nxt.first][nxt.second]) {
                        continue;
                    }
                }
                // cerr << s.first << ' ' << s.second << ' ' << e.first << ' ' << e.second << ' ' << s1.first << ' ' << s1.second << ' ' << e1.first << ' ' << e1.second << endl;
                if(!grid[e1.first][e1.second]) {
                    continue;
                }
                if(vis[s1.first][s1.second][e1.first][e1.second]) {
                    continue;
                }
                vis[s1.first][s1.second][e1.first][e1.second] = 1;
                parop[s1.first][s1.second][e1.first][e1.second] = d;
                parnode[s1.first][s1.second][e1.first][e1.second] = {s, e};
                q.push({s1, e1});
            }
        }
    }
}

void solve() {
    int n, m;
    cin >> n >> m;
    vvb grid(n+2, vb(m+2));
    for(int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < m; j++) {
            grid[i][j+1] = (s[j]-'0');
        }
    }
    
    pii start, end;
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        start = {x1, y1};
        end = {x2, y2};
    }

    vi tour_seq;
    vvb vis1(n+2, vb(m+2));
    dfs(start, vis1, grid, tour_seq);

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(grid[i][j] && !vis1[i][j]) {
                cout << "-1" << endl;
                return;
            }
        }
    }

    // for(int i : tour_seq) {
    //     cerr << ops[i];
    // }
    // cerr << endl;

    pii start2 = follow(start, tour_seq, grid, false);
    pii end2 = follow(end, tour_seq, grid, true);

    // start -> start2
    // end -> end2
    find_path(grid, start, end);
    assert(vis[start2.first][start2.second][end2.first][end2.second]);
    vi path1;
    pair<pii, pii> cur = {start2, end2};
    while(cur != make_pair(start, end)) {
        // cerr << cur.first.first << ' ' << cur.first.second << ' ' << cur.second.first << ' ' << cur.second.second << endl;
        path1.push_back(parop[cur.first.first][cur.first.second][cur.second.first][cur.second.second]);
        cur = parnode[cur.first.first][cur.first.second][cur.second.first][cur.second.second];
    }
    reverse(path1.begin(), path1.end());

    
    // cerr << end2.first << ' ' << end2.second << endl;


    // cerr << "loop done" << endl;

    find_path(grid, start2, end2);

    pii goodp = {-1, -1};
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            if(vis[i][j][i][j]){
                goodp = {i, j};
            }
        }
    }
    assert(goodp.first != -1);
    // cerr << goodp.first << ' ' << goodp.second << endl;

    vi revseq;
    cur = {goodp, goodp};
    while(cur != make_pair(start2, end2)) {
        // cerr << cur.first.first << ' ' << cur.first.second << ' ' << cur.second.first << ' ' << cur.second.second << endl;
        revseq.push_back(parop[cur.first.first][cur.first.second][cur.second.first][cur.second.second]);
        cur = parnode[cur.first.first][cur.first.second][cur.second.first][cur.second.second];
    }
    reverse(revseq.begin(), revseq.end());
    // cout << tour_seq << revseq << endl;
    string out = "";
    for(int i : path1) {
        out += ops[i];
    }
    // out += "|";
    for(int i : tour_seq) {
        out += ops[i];
    }
    // out += "|";
    for(int i : revseq) {
        out += ops[i];
    }
    // out += "|";
    cout << out;
    reverse(out.begin(), out.end());
    cout << out;
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 27884kb

input:

2 2
11
11
1 1 2 2

output:

DRUDLUDRRDULDURD

result:

ok Valid Solution (Length = 16).

Test #2:

score: 0
Accepted
time: 1ms
memory: 3732kb

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: 0
Accepted
time: 0ms
memory: 28092kb

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

score: 0
Accepted
time: 0ms
memory: 28056kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

DDDULLRUUURDDDDRUUUUDDDDLLLUUUUDDDDRRUUUULDDDUUUDDDDLRRRRRRLDDDDUUUDDDLUUUURRDDDDUUUULLLDDDDUUUURDDDDRUUURLLUDDD

result:

ok Valid Solution (Length = 112).

Test #5:

score: 0
Accepted
time: 3ms
memory: 27832kb

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

RRRRLRDDDDLLUUUULLDDDDRLUURLUURRDDRLDDRRUUUULRDDDLLLLDDLLLLDDDRLUUUURRDDLRDDRRUULRUULRDDDDLLUUUULLDDDDRLRRRR

result:

ok Valid Solution (Length = 108).

Test #6:

score: 0
Accepted
time: 5ms
memory: 27816kb

input:

5 3
111
100
111
001
111
4 3 3 2

output:

URDULLUURRLLDDRRDDLLRRUUDLDLUURRUULDLDUURRLLDDRRDDLLRRUULLUDRU

result:

ok Valid Solution (Length = 62).

Test #7:

score: 0
Accepted
time: 3ms
memory: 27808kb

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

ULRUDRDDURUUUDDDLULLUUDDRUDRDLLUUDDDDUULLDRDURDDUULLULDDDUUURUDDRDURLU

result:

ok Valid Solution (Length = 70).

Test #8:

score: 0
Accepted
time: 0ms
memory: 28076kb

input:

5 3
101
111
100
111
100
4 1 2 2

output:

ULDUUUDRRUDLLDDDURRLLURDRUUULDDLUUURDRULLRRUDDDLLDURRDUUUDLU

result:

ok Valid Solution (Length = 60).

Test #9:

score: 0
Accepted
time: 3ms
memory: 27816kb

input:

5 5
01110
10110
11110
11011
11100
2 4 5 1

output:

DDDUUULDDRDRLULLDDRLLUUUDDDRUURUULRRDUDDLLDDRRDDLLDDUDRRLUURUURDDDUUULLRDDLLULRDRDDLUUUDDD

result:

ok Valid Solution (Length = 90).

Test #10:

score: 0
Accepted
time: 3ms
memory: 27884kb

input:

5 3
011
111
110
111
011
3 1 2 1

output:

UUDLLURURDULDDDDRUDLULRUULDUDDRDRRDRDDUDLUURLULDURDDDDLUDRURULLDUU

result:

ok Valid Solution (Length = 66).

Test #11:

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

input:

4 5
11111
11111
11111
11111
3 2 1 3

output:

UUUDDLLRUURDDDRUUURDDDUUULDDDLLLUUUDDDRRUUULDDUUDDDLRRRRRRRRLDDDUUDDLUUURRDDDUUULLLDDDLUUUDDDRUUURDDDRUURLLDDUUU

result:

ok Valid Solution (Length = 112).

Test #12:

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

input:

5 5
11111
10101
11111
10101
11111
2 5 1 1

output:

UUUUDULLDDDDRRUULRDDLLLLUUUURLDDRLDDRRUUUURRDUDDDLLLLDDLLLLDDDUDRRUUUURRDDLRDDLRUUUULLLLDDRLUURRDDDDLLUDUUUU

result:

ok Valid Solution (Length = 108).

Test #13:

score: 0
Accepted
time: 3ms
memory: 27860kb

input:

4 5
11111
10000
11111
00001
1 3 4 5

output:

RRLLLLDDRRRRDULLLLUURRLLDDRRRRDDRRRRDDLLRRUULLLLUDRRRRDDLLLLRR

result:

ok Valid Solution (Length = 62).

Test #14:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

3 5
10100
00010
00111
1 3 1 1

output:

-1

result:

ok No Solution.

Test #15:

score: 0
Accepted
time: 0ms
memory: 27824kb

input:

4 5
10001
11111
11100
11111
4 5 3 1

output:

DLLUURRUDLLLDDLUUUDDDRUURDDRRUULLLLRRRRRRRRLLLLUURRDDRUURDDDUUULDDLLLDURRUULLD

result:

ok Valid Solution (Length = 78).

Test #16:

score: 0
Accepted
time: 3ms
memory: 27880kb

input:

3 5
11111
10100
11111
1 2 3 5

output:

RRDLULRDDRRLLLLUUDDRRUURRLLLRDLLDRRRRDLLDRLLLRRUURRDDUULLLLRRDDRLULDRR

result:

ok Valid Solution (Length = 70).

Test #17:

score: 0
Accepted
time: 0ms
memory: 3496kb

input:

4 5
01110
10101
11011
10111
1 3 2 3

output:

-1

result:

ok No Solution.

Test #18:

score: 0
Accepted
time: 3ms
memory: 27904kb

input:

5 5
11111
11111
11111
11111
11111
1 3 5 2

output:

LLLRRDDDDRUUUURDDDDUUUULDDDDLLUUUULDDDDUUUURDDDDRUUUUDDDDLLRRRRRRRRLLDDDDUUUURDDDDRUUUUDDDDLUUUULLDDDDLUUUUDDDDRUUUURDDDDRRLLL

result:

ok Valid Solution (Length = 126).

Test #19:

score: 0
Accepted
time: 3ms
memory: 27840kb

input:

5 5
11111
10101
11111
10101
11111
5 1 2 3

output:

DLLUUUURRDDDDRRUUUULRDDLRDDLLLRUULRUULLDDDDRUUUURRRRRRUUUURDDDDLLUURLUURLLLDDRLDDRLUUUURRDDDDRRUUUULLD

result:

ok Valid Solution (Length = 102).

Test #20:

score: 0
Accepted
time: 0ms
memory: 27888kb

input:

5 5
11111
10000
11111
00001
11111
4 5 5 3

output:

ULLDDRRRRDULLLLUURRRRLLLLDDRRRRDDLLLLRRRRUUDLLLDLUURRUULDLLLDUURRRRLLLLDDRRRRDDLLLLRRRRUULLLLUDRRRRDDLLU

result:

ok Valid Solution (Length = 104).

Test #21:

score: 0
Accepted
time: 0ms
memory: 3732kb

input:

5 5
01010
10101
10101
11001
10011
4 1 5 4

output:

-1

result:

ok No Solution.

Test #22:

score: 0
Accepted
time: 3ms
memory: 28080kb

input:

5 5
10101
11111
10101
11111
11111
3 1 2 4

output:

DLUUUDRRUDDDDRURUUUDLRDDDULDLLULDURDRUUULLDURURDDDRRRRDDDRURUDLLUUURDRUDLULLDLUDDDRLDUUURURDDDDURRDUUULD

result:

ok Valid Solution (Length = 104).

Test #23:

score: 0
Accepted
time: 3ms
memory: 27920kb

input:

5 5
00001
11111
01110
01111
01111
1 5 5 2

output:

DLDDDRUDLLUUULDDDUUULRRDDDRUUURULLDLDDDRRDDDLDLLURUUURDDDRRLUUUDDDLUUULLDURDDDLD

result:

ok Valid Solution (Length = 80).

Test #24:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

5 5
01011
10111
11011
10101
01110
4 1 2 3

output:

-1

result:

ok No Solution.

Test #25:

score: 0
Accepted
time: 0ms
memory: 28084kb

input:

10 8
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
7 7 3 6

output:

UUUUUUUDDDDDDRRRRRLUUUUUURDDDDDDDDDLUULUUUUUUULDDDDDDDDDRUDLLUUUUUUUUULDDDDDDDDDLUUUUUUUUULDDDDDDDDDUUUUUUUUURDDDDDDDDDRUUUUUUUUURDDDDDDDDDRUUUUUUUUURDDDDDDDRDDRUUUUUUUUULDDDDDDUUUUUUDDDDDDDDDLLLLLLRRRRRRRRRRRRRRLLLLLLDDDDDDDDDUUUUUUDDDDDDLUUUUUUUUURDDRDDDDDDDRUUUUUUUUURDDDDDDDDDRUUUUUUUUURDDDDDDDDD...

result:

ok Valid Solution (Length = 410).

Test #26:

score: 0
Accepted
time: 2ms
memory: 27916kb

input:

10 6
111111
101010
111111
101010
111111
101010
111111
101010
111111
101010
1 6 2 3

output:

UUUUUUULDLURLDDDDDDDDDURLLLUUUUUUUURLLLDDDDDDDDDURLUURLUURLUURLUURRDDRLDDRLDDRLDDDURRUURLUURLUURLUURLDDDDDDDDDDDDDDDDDDLRUULRUULRUULRUURRUDDDLRDDLRDDLRDDRRUULRUULRUULRUULRUDDDDDDDDDLLLRUUUUUUUULLLRUDDDDDDDDDLRULDLUUUUUUU

result:

ok Valid Solution (Length = 220).

Test #27:

score: 0
Accepted
time: 8ms
memory: 27868kb

input:

10 10
1111111111
1000000000
1111111111
0000000001
1111111111
1000000000
1111111111
0000000001
1111111111
1000000000
5 5 5 2

output:

RUULLLLLLLLLUURRRRRRRRRUULLLLLLLLLUURRRRRRRRRLLLLLLLLLDDRRRRRRRRRDDLLLLLLLLLDDRRRRRRRRRDDLLLLLLLLLDURRRRRRRRRUULLLLLLLLLUURRRRLLLLDDRRRRRRRRRUDDLLLLLLLLLDDLLLLLLLLLDDURRRRRRRRRDDLLLLRRRRUULLLLLLLLLUURRRRRRRRRUDLLLLLLLLLDDRRRRRRRRRDDLLLLLLLLLDDRRRRRRRRRDDLLLLLLLLLRRRRRRRRRUULLLLLLLLLUURRRRRRRRRUULLLL...

result:

ok Valid Solution (Length = 308).

Test #28:

score: 0
Accepted
time: 1ms
memory: 3504kb

input:

10 10
1010110101
0000011010
1001001001
0011111000
1000111100
1011101001
1100110011
0110001011
0011111000
0101011101
7 5 4 3

output:

-1

result:

ok No Solution.

Test #29:

score: 0
Accepted
time: 0ms
memory: 27920kb

input:

10 6
100100
111111
100001
111111
101111
111111
101010
111111
111100
111111
6 5 7 3

output:

DDDULLULDRUURUULLUDLLLUDDDDDDDDDRUURUUUURDDUULLRDDLRDDDDRUURUDRLLDDRRLLLUULDDLUUUUUUUURRRRRDDDDUULDDUUUDDDDRUURUULLDDRRRRDDLLUURUURDDDDUUUDDLUUDDDDRRRRRUUUUUUUULDDLUULLLRRDDLLRDURUURDDDDRLDDRLLUUDDRUUUURUURDDDDDDDDDULLLDULLUURUURDLULLUDDD

result:

ok Valid Solution (Length = 238).

Test #30:

score: -100
Wrong Answer
time: 4ms
memory: 28108kb

input:

10 8
11111110
11110111
01111111
11111101
11011101
11111111
11111011
11011101
11001111
11111110
7 1 2 1

output:

LUUUUULLUDDDLLUUURUUURDDDRUUURRDDDDDRDRUUUUULUDDURDDDDDDDLDLUULUUUUUDDLDDDULULUDDDDDRRRUDLLLLUUDDRUUUURDRUURDDDRDDRURUULULUUUUULLDDDLUUULLDURDDDLDDDUUDDDDDLRRRRRRRRRRRRLDDDDDUUDDDLDDDRUDLLUUULDDDLLUUUUULULUURURDDRDDDRUURDRUUUURDDUULLLLDURRRDDDDDULULUDDDLDDUUUUULUULDLDDDDDDDRUDDULUUUUURDRDDDDDRRUUURD...

result:

wrong answer End Point Is (1,3), Not (er = 2, ec = 1)