QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #479226 | #7751. Palindrome Path | ucup-team052# | WA | 13ms | 64564kb | C++14 | 3.6kb | 2024-07-15 16:01:29 | 2024-07-15 16:01:29 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
const char dc[4] = {'D', 'U', 'R', 'L'};
const int N = 905;
struct atom {
int x, y, d;
atom (int a = 0, int b = 0, int c = 0) : x(a), y(b), d(c) {}
};
char c[35][35];
queue < pair <int, int> > q;
vector <atom> adj[N][N], radj[N][N];
vector <int> ans;
int frx[N][N], fry[N][N], fr[N][N], vis[N][N];
int frx2[N][N], fry2[N][N], fr2[N][N], vis2[N][N], vis3[N][N];
int n, m, sx, sy, tx, ty;
inline int s(int x, int y) { return (x - 1) * m + y; }
int seq[N * N], len;
void solve(int x, int y) {
if (!frx[x][y]) return;
solve(frx[x][y], fry[x][y]);
seq[++len] = fr[x][y];
}
void solve2(int x, int y) {
if (!frx2[x][y]) return;
seq[++len] = fr2[x][y];
solve2(frx2[x][y], fry2[x][y]);
}
void go(int &x, int &y, int d) {
int tx = x + dx[d], ty = y + dy[d];
if (tx >= 1 && tx <= n && ty >= 1 && ty <= m && c[tx][ty] == '1') x = tx, y = ty;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", c[i] + 1);
scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
q.push(make_pair(s(sx, sy), s(tx, ty))); vis[s(sx, sy)][s(tx, ty)] = 1;
while (!q.empty()) {
pair <int, int> t = q.front(); q.pop();
int ux1 = (t.first - 1) / m + 1, uy1 = (t.first - 1) % m + 1;
int ux2 = (t.second - 1) / m + 1, uy2 = (t.second - 1) % m + 1;
for (int d = 0; d < 4; d++) {
for (int i = 0; i <= 1; i++) {
int x1, y1, x2, y2;
x1 = ux1 + dx[d]; y1 = uy1 + dy[d];
if (x1 < 1 || x1 > n || y1 < 1 || y1 > m || c[x1][y1] == '0') x1 = ux1, y1 = uy1;
if (i) {
x2 = ux2 + dx[d ^ 1], y2 = uy2 + dy[d ^ 1];
if (x2 < 1 || x2 > n || y2 < 1 || y2 > m || c[x2][y2] == '0') continue;
} else {
x2 = ux2 + dx[d], y2 = uy2 + dy[d];
if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && c[x2][y2] == '1') continue;
x2 = ux2; y2 = uy2;
}
int t1 = s(x1, y1), t2 = s(x2, y2);
adj[t.first][t.second].push_back(atom(t1, t2, d));
radj[t1][t2].push_back(atom(t.first, t.second, d));
if (vis[t1][t2]) continue;
vis[t1][t2] = 1; frx[t1][t2] = t.first; fry[t1][t2] = t.second; fr[t1][t2] = d; q.push(make_pair(t1, t2));
}
}
}
q.push(make_pair(s(sx, sy), s(tx, ty))); vis2[s(sx, sy)][s(tx, ty)] = 1;
while (!q.empty()) {
pair <int, int> t = q.front(); q.pop();
for (auto v : radj[t.first][t.second]) {
int t1 = v.x, t2 = v.y;
if (vis2[t1][t2]) continue;
vis2[t1][t2] = 1; frx2[t1][t2] = t.first; fry2[t1][t2] = t.second; fr2[t1][t2] = v.d; q.push(make_pair(t1, t2));
}
}
vis3[sx][sy] = 1;
int nx = sx, ny = sy;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (c[i][j] == '0' || vis3[i][j]) continue;
int tt = s(i, j);
for (int k = 1; k <= n * m; k++) {
if (vis[tt][k] && vis2[tt][k]) {
len = 0;
solve(tt, k); solve2(tt, k);
for (int t = 1; t <= len; t++) {
ans.push_back(seq[t]);
go(nx, ny, seq[t]); vis3[nx][ny] = 1;
}
assert(nx == sx && ny == sy);
break;
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int t = s(i, j);
if (vis[t][t]) {
solve(t, t);
for (int k = 1; k <= len; k++) ans.push_back(seq[k]);
for (auto i : ans) printf("%c", dc[i]), go(nx, ny, i);
reverse(ans.begin(), ans.end());
for (auto i : ans) printf("%c", dc[i]), go(nx, ny, i);
assert(nx == tx && ny == ty);
// for (int k = len; k >= 1; k--) printf("%c", dc[seq[k]]);
return 0;
}
}
}
printf("-1\n");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 61648kb
input:
2 2 11 11 1 1 2 2
output:
DURULDRLUDRLUDURLLRUDULRDULRDLURUD
result:
ok Valid Solution (Length = 34).
Test #2:
score: 0
Accepted
time: 0ms
memory: 49992kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 3ms
memory: 49236kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 4ms
memory: 64564kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
DDDUUUURLLUUUUDDLLRDDDDUUUULLRRRLUUUUDDLDDDDUUULLRRRLUUUUDDLDDDDUULLRRRLUUUUDDLDDDDURLLUUUUDDLLRDDDDULLRRRLUUUUDDLDDDDRLLUUUUDDLLRDDDDLLRRRLUUUUDDLDDDDLLRRRLUUUUDDLDDDDUUUURLLLLRUUUUDDDDLDDUUUULRRRLLDDDDLDDUUUULRRRLLDDDDRLLDDUUUULLRDDDDLDDUUUULRRRLLUDDDDRLLDDUUUULLRUDDDDLDDUUUULRRRLLUUDDDDLDDUUUULRR...
result:
ok Valid Solution (Length = 350).
Test #5:
score: 0
Accepted
time: 7ms
memory: 64316kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
DDDDRRRRLLLLLLLLRRRUUUUDDDLLLDRRRRLLLLURRRUUUDDDLDRRRRLLLLURUUUDDDDRDRRRLLLULUUUUDLDRRRRDLDLUULLLLRRRUUDDRRDDRRLLULLLURUUUDLDDLLDRRRRLLLLURRUURUDLDDDRRRRLLLLUUURUDDRDRDDRRLLUULULUURRDDDDRRLLLLUULLLLRRUURRRDDDDRRLLLLUULLLLRRUURDDDDRRRRLLLLLLLLRRRRDDDDRUURRLLLLUULLLLRRDDDDRRRUURRLLLLUULLLLRRDDDDRRUULU...
result:
ok Valid Solution (Length = 476).
Test #6:
score: 0
Accepted
time: 4ms
memory: 61948kb
input:
5 3 111 100 111 001 111 4 3 3 2
output:
URLDDLUUUUDDLLRRDURLDDLUURUULDDLRRDURLLUURDRDLUULDDLRRDRDDLLURRULRDDLLURRULURLDDLUUUULDDLRULURRULLDDRLURRULLDDRDRRLDDLUULDRDRUULLRUDRRLDDLUURUULDDLRUDRRLLDDUUUULDDLRU
result:
ok Valid Solution (Length = 166).
Test #7:
score: 0
Accepted
time: 3ms
memory: 64188kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
LUUDRUDRRUUUUDDLLUUDLURUDRUDULUUDRUDRULLUUDRUUDDUULUUDRUUDDUULULUULULUUDDUURDUULUUDDUURDUULLURDURDUULUDURDURULDUULLDDUUUURRDURDUUL
result:
ok Valid Solution (Length = 130).
Test #8:
score: 0
Accepted
time: 0ms
memory: 61308kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
UUURDUULDDDUURDRUUDLULDDRDULRDRLULDRDULDRDULUUURDUUDRUUULUDRDLUDRDLULRDRLUDRDDLULDUURDRUUDDDLUUDRUUU
result:
ok Valid Solution (Length = 100).
Test #9:
score: 0
Accepted
time: 3ms
memory: 64060kb
input:
5 5 01110 10110 11110 11011 11100 2 4 5 1
output:
DLDUULDDRLLUURUUDRDDLULDDUURLUURUUDRDLDLLDDUUURLUUDRURRUDLDLDDURDLUURURRUDDLLDDRLUURUUDRDLDLDDRLUURUUDRDLDLDDRLUURUUDRDLDUULDDRLLRDDLUUDLDRDUURUULRDDLDLDRDUURUULRDDLDLDRDUURUULRDDLLDDURRURUULDRUDDLDLDURRURDUULRUUUDDLLDLDRDUURUULRUUDDLULDDRDUURUULLRDDLUUDLD
result:
ok Valid Solution (Length = 256).
Test #10:
score: 0
Accepted
time: 13ms
memory: 64004kb
input:
5 3 011 111 110 111 011 3 1 2 1
output:
ULDULRUUUUDDRLULLRRDULUDDRRLLDURLLDLRURLLDLRRLURLLLDRDUURLLLDRDRULURLLLDRDRULURLULDULRUURLUDLULRULURDRDLLLRULURDRDLLLRUUDRDLLLRULRRLDLLRURLDLLRUDLLRRDDULUDRRLLULRDDUUUURLUDLU
result:
ok Valid Solution (Length = 174).
Test #11:
score: 0
Accepted
time: 3ms
memory: 62200kb
input:
4 5 11111 11111 11111 11111 3 2 1 3
output:
UURRLLLLLLRUUDDUULLRRRRLLLUUDDURRLLLLLLRUUDDULLRRRRLLLUUDDRRLLLLLLRLLRRRRLLLUUUDDDRRLLLULLLRUUUDDDLLRRRRULLLUUUDDDLLRRRRULLLUURRLLLLLLRRUULLLURRRRLLDDDUUULLLURRRRLLDDDUUURLLLULLLRRDDDUUULLLRRRRLLRLLLLLLRRDDUULLLRRRRLLUDDUURLLLLLLRRUDDUULLLRRRRLLUUDDUURLLLLLLRRUU
result:
ok Valid Solution (Length = 262).
Test #12:
score: 0
Accepted
time: 0ms
memory: 60680kb
input:
5 5 11111 10101 11111 10101 11111 2 5 1 1
output:
ULLLLURRRRDULLLLDURRRRDULLDURRDLDRLLLLUURRRRDULLLLDDDRUUURRRRDULLDDDRUUURRDLDDRUULDDDRLLLLUUUURRRRDLDDDRLLLLUUUURRRRDULLLLLLLLUDRRRRUUUULLLLRDDDLDRRRRUUUULLLLRDDDLUURDDLDRRUUURDDDLLUDRRRRUUURDDDLLLLUDRRRRUULLLLRDLDRRUDLLUDRRRRUDLLLLUDRRRRULLLLU
result:
ok Valid Solution (Length = 244).
Test #13:
score: 0
Accepted
time: 6ms
memory: 61556kb
input:
4 5 11111 10000 11111 00001 1 3 4 5
output:
DRRRRDDLLLLUULLLLRRULLDRRRRDDUUULLLLRRULLDRRRDRDDLUULLLLRRULLDRRDRRDDUULLLLUURRLLDRDRRRDDUULLLLUURRLLDDRRRRDDUUULLLLUURRLLDDRRRRDDUUULLLLUURRDRRRRDDLLLLLLLLDDRRRRDRRUULLLLUUUDDRRRRDDLLRRUULLLLUUUDDRRRRDDLLRRUULLLLUUDDRRRDRDLLRRUULLLLUUDDRRDRRDLLURRLLLLUULDDRDRRRDLLURRLLLLUUUDDRRRRDLLURRLLLLUULLLLDDR...
result:
ok Valid Solution (Length = 304).
Test #14:
score: 0
Accepted
time: 3ms
memory: 48780kb
input:
3 5 10100 00010 00111 1 3 1 1
output:
-1
result:
ok No Solution.
Test #15:
score: 0
Accepted
time: 9ms
memory: 62096kb
input:
4 5 10001 11111 11100 11111 4 5 3 1
output:
DDLLUULLUUDRRUUDDRRUUDDLLUURRUUUUDLLDDRRDDLLULLRRUUDDRRUUDDLLLLRRRRUUDDLLLLRRRRUUDDLLUULLUULLUULLDDUURRRRLLLLDDUURRRRLLLLDDUURRDDUURRLLULLDDRRDDLLDUUUURRUULLDDUURRDDUURRDUULLUULLDD
result:
ok Valid Solution (Length = 180).
Test #16:
score: 0
Accepted
time: 3ms
memory: 62132kb
input:
3 5 11111 10100 11111 1 2 3 5
output:
RRDDRRLLLLLLUULLRRRDLLLDRRLLUULLRRRDLDRRLLURULLRDRRRDDLLLLUULLRRDRDDRRLLLURULULRDRDDRRLLLURULULRRDDRRLLLLLLLLRRDDRRLULURULLLRRDDRDRLULURULLLRRDDRDRRLLUULLLLDDRRRDRLLURULLRRDLDRRRLLUULLRRDLLLDRRRLLUULLLLLLRRDDRR
result:
ok Valid Solution (Length = 210).
Test #17:
score: -100
Wrong Answer
time: 3ms
memory: 64308kb
input:
4 5 01110 10101 11011 10111 1 3 2 3
output:
DRULLURDURLUDURLUDRULLURDULRUDULRUDRULLURD
result:
wrong answer (2,1) Not Visited