QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #333190 | #7751. Palindrome Path | sumi007 | WA | 0ms | 3904kb | C++14 | 3.3kb | 2024-02-19 17:57:00 | 2024-02-19 17:57:00 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define i64 __int128
#define db double
#define ldb long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(i) (i&-i)
const int N = 55;
int n,m,idx,sx,sy,ex,ey,st,ed,las[N*N],a[N][N],id[N][N],fa[N*N],vis[N*N];
int dis[N*N][4],typ[N][N];
char opt[5] = {'W','U','R','L','D'};
vector<char> ans;
vector<int> e[N*N];
int find(int u){
if(u==fa[u]) return u;
return fa[u] = find(fa[u]);
}
void merge(int u,int v){
e[u].pb(v),e[v].pb(u);
u = find(u),v = find(v);
if(u==v) return ;
fa[u] = v;
}
void move(int u,int v){
int w = typ[u][v];
int ds = dis[u][5-w],dt = dis[ed][w];
if(dt<=ds){
for(int i=1;i<=dt;i++) ans.pb(opt[5-w]);
for(int i=1;i<=dt+1;i++) ans.pb(opt[w]);
}else{
for(int i=1;i<=ds+1;i++) ans.pb(opt[5-w]);
for(int i=1;i<=ds+1;i++) ans.pb(opt[w]);
}
}
void dfs(int u){
vis[u] = 1;
for(int v:e[u]){
if(vis[v]) continue;
move(u,v);
las[v] = u;
dfs(v);
move(v,u);
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char ch;cin >> ch;
a[i][j] = ch-'0';
if(a[i][j]) id[i][j] = ++idx;
}
}
cin >> sx >> sy >> ex >> ey;
st = id[sx][sy],ed = id[ex][ey];
if(!st || !ed) cout << -1,exit(0);
for(int i=1;i<=idx;i++) fa[i] = i;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int u = id[i][j];
if(a[i][j] && a[i+1][j]) merge(id[i][j],id[i+1][j]);
if(a[i][j] && a[i][j+1]) merge(id[i][j],id[i][j+1]);
typ[u][id[i+1][j]] = 4,typ[id[i+1][j]][u] = 1;
typ[u][id[i][j+1]] = 2,typ[id[i][j+1]][u] = 3;
}
}
for(int i=1;i<=idx;i++) fa[i] = find(i);
for(int i=1;i<idx;i++) if(fa[i]!=fa[i+1]) cout << -1,exit(0);
for(int i=1;i<=n;i++){
for(int j=m;j>=1;j--){
int u = id[i][j],v = id[i][j+1];
if(!u) continue;
if(!v) dis[u][2] = 0;
else dis[u][2] = dis[v][2]+1;
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=m;j++){
int u = id[i][j],v = id[i+1][j];
if(!u) continue;
if(!v) dis[u][4] = 0;
else dis[u][4] = dis[v][4]+1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int u = id[i][j],v = id[i-1][j];
if(!u) continue;
if(!v) dis[u][1] = 0;
else dis[u][1] = dis[v][1]+1;
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int u = id[i][j],v = id[i][j-1];
if(!u) continue;
if(!v) dis[u][3] = 0;
else dis[u][3] = dis[v][3]+1;
}
}
dfs(st);
stack<int> stk;int now = ed;
while(now!=st) stk.push(now),now = las[now];
stk.push(st);
while(stk.size()>1){
int u = stk.top();stk.pop();
move(u,stk.top());
}
for(char x:ans) cout << x;
reverse(ans.begin(),ans.end());
for(char x:ans) cout << x;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3864kb
input:
2 2 11 11 1 1 2 2
output:
DRDUDRLDUDRRDUDLRDUDRD
result:
ok Valid Solution (Length = 22).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
DDUUDDDUUUDDDUUUURLLUDUDDUDDUDDLRLLRRDUDDUUDDDUUUDDDUUUULLRRRUDUDDUDDUDDDUDDUUDDDUUUDDDUUUURLUDUDDUDDUDDRLLRLLDUDDUUDDDUUUDDDUUUULRUDUDDUDDDDUDDUDURLUUUUDDDUUUDDDUUDDUDLLRLLRDDUDDUDDUDULRUUUUDDDUUUDDDUUDDUDDDUDDUDDUDURRRLLUUUUDDDUUUDDDUUDDUDRRLLRLDDUDDUDDUDULLRUUUUDDDUUUDDDUUDD
result:
ok Valid Solution (Length = 278).
Test #5:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
RRLLRRRLLLRRRRLLLLDDDDRRDUDDUUDDDUUUDRRRLLLRRRDDDUUUDDDDUUUUDDDDRLRDUDDUURLRRLLDDRRRLLLRRRRLLLLDUDDUUDDDUUUDDDDUUUURRRRRLLRRRLLLRRRRLLLLDDDDRRDUDDUURRDDDDRRUUDDUDRRDDDDLLLLRRRRLLLRRRLLRRRRRUUUUDDDDUUUDDDUUDDUDLLLLRRRRLLLRRRDDLLRRLRUUDDUDRLRDDDDUUUUDDDDUUUDDDRRRLLLRRRDUUUDDDUUDDUDRRDDDDLLLLRRRRLLLRRR...
result:
ok Valid Solution (Length = 304).
Test #6:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
5 3 111 100 111 001 111 4 3 3 2
output:
URLRLLUULRLRRRLRLLDDLRLRRDDRLRLLLRLRRUURLLRUURRLRLLLRLRDDRRLRLDDLLRLRRRLRLUULLRLRU
result:
ok Valid Solution (Length = 82).
Test #7:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
LUUDUUDDRRUDUUDDURUUUUDUUDDUUDDDLULLURLUULRULLULDDDUUDDUUDUUUURUDDUUDURRDDUUDUUL
result:
ok Valid Solution (Length = 80).
Test #8:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
UUUDLRLRRUDRLRLLDDDULRLRRRLRLLUULRRLUULLRLRRRLRLUDDDLLRLRDURRLRLDUUU
result:
ok Valid Solution (Length = 68).
Test #9:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
5 5 01110 10110 11110 11011 11100 2 4 5 1
output:
DDDUUULLLRDDLLDDDUUUDDDLRDUDLLRRLLDUDDUULRLLRRLLRRRDLRLDULDUDDUULLRRDDDDUUULDDLLDDDDLLDDLUUUDDDDRRLLUUDDUDLUDLRLDRRRLLRRLLRLUUDDUDLLRRLLDUDRLDDDUUUDDDLLDDRLLLUUUDDD
result:
ok Valid Solution (Length = 164).
Test #10:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
5 3 011 111 110 111 011 3 1 2 1
output:
ULRULRUDULUDUUDDUUDDDLLRUUDDDLRUUDLUUULUDUUDULUUULDUURLDDDUURLLDDDUUDDUUDULUDURLURLU
result:
ok Valid Solution (Length = 84).
Test #11:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
4 5 11111 11111 11111 11111 3 2 1 3
output:
UURRLLLUDUUDDUUUDDDLRLLRRUUULLRRRUDUUDDUUUDDDLLRRRUUUUDUUDDUUUDDDRLUUURRLLUDUUDDUUUDDDRRLLLRRLLLUUULRUDUUDDUURRLLLUDUUDDUUUDDDLRLLRRUUUUUURRLLRLDDDUUUDDUUDULLLRRUUDDUUDURLUUULLLRRLLLRRDDDUUUDDUUDULLRRUUULRDDDUUUDDUUDUUUURRRLLDDDUUUDDUUDURRRLLUUURRLLRLDDDUUUDDUUDULLLRRUU
result:
ok Valid Solution (Length = 270).
Test #12:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
5 5 11111 10101 11111 10101 11111 2 5 1 1
output:
ULLLLUDUUDDUUUDDDUUUUDDDDLRLLRRUUUUUDDLLLRRLLLRRRLLLLRRRRUUUDDDUUUUDDDDLLLLLRRRRUULLUUUDDDUUUUDDDDLLUUUULRLLRRLLLRRRLLLLRRRRUDULLLLLLLLUDURRRRLLLLRRRLLLRRLLRLUUUULLDDDDUUUUDDDUUULLUURRRRLLLLLDDDDUUUUDDDUUURRRRLLLLRRRLLLRRLLLDDUUUUURRLLRLDDDDUUUUDDDUUUDDUUDULLLLU
result:
ok Valid Solution (Length = 262).
Test #13:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
4 5 11111 10000 11111 00001 1 3 4 5
output:
LLDDRRRRDDULLLLDUDUURRRRLLLLDDRRRRDDRRRRDDLLLLRRRRUUDUDLLLLUDDRRRRDDLL
result:
ok Valid Solution (Length = 70).
Test #14:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
3 5 10100 00010 00111 1 3 1 1
output:
-1
result:
ok No Solution.
Test #15:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
4 5 10001 11111 11100 11111 4 5 3 1
output:
LLDUDDUULLDDUUUUDUDDUDDLRDUUDDLDUDDUULRLLRRLLRRRLLRRRDUUDLLUDUDDLLRRRLLRRRLLDUDDUULLUDDDDULLUUDDUDLLRRRLLRRRLLDDUDULLDUUDRRRLLRRRLLRRLLRLUUDDUDLDDUUDRLDDUDDUDUUUUDDLLUUDDUDLL
result:
ok Valid Solution (Length = 174).
Test #16:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
3 5 11111 10100 11111 1 2 3 5
output:
RRRRLLLLDDRRUURRRLRRLLDDRRRLRRLLRRRLLLRRRRLLLLUURRRRRLLLLDDRRRRRRRRDDLLLLRRRRRUULLLLRRRRLLLRRRLLRRLRRRDDLLRRLRRRUURRDDLLLLRRRR
result:
ok Valid Solution (Length = 126).
Test #17:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
4 5 01110 10101 11011 10111 1 3 2 3
output:
-1
result:
ok No Solution.
Test #18:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
5 5 11111 11111 11111 11111 11111 1 3 5 2
output:
RLLRLLDDDDLRDUDDUUDDDUUULLRRDDDLLLRRRDUDDUUDDDUUUDDDDUUUULLLRRRRDDDDDUDDUUDDDUUUDDDDUUUURLDDDDRLLDUDDUUDDDUUURLLDDDRLLDUDDUUDDDUUUDDDDUUUULRLLRRRLLRLLDDDDLRRLDDDDLLRLLRRRLLRLUUUUDDDDUUUDDDUUDDUDLLRDDDLLRUUUDDDUUDDUDLLRDDDDLRUUUUDDDDUUUDDDUUDDUDDDDDRRRRLLLUUUUDDDDUUUDDDUUDDUDRRRLLLDDDRRLLUUUDDDUUDDUD...
result:
ok Valid Solution (Length = 312).
Test #19:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
5 5 11111 10101 11111 10101 11111 5 1 2 3
output:
DUDUUDUUDUURRUDUUDDLRUUUDDDUUUDDDDLRRRDUDUUDUUDUULRUDUUDDLRUUUDDDUUUDDDDLLDUDUUDUUDUULLUDUUDDUUUDDDUUUDDDDDUDUUDUUDUURRUDDURRUUDUUDUUDUDDDDDUUUDDDUUUDDUUDULLUUDUUDUUDUDLLDDDDUUUDDDUUURLDDUUDURLUUDUUDUUDUDRRRLDDDDUUUDDDUUURLDDUUDURRUUDUUDUUDUD
result:
ok Valid Solution (Length = 242).
Test #20:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
5 5 11111 10000 11111 00001 11111 4 5 5 3
output:
URLRRLLRRLLLRRLLLUULRLLRRLLRRRLLRRRRLRRLLRRLLLRRLLLDDLRLLRRLLRRRLLRRRDDRLRRLLRRLLLRRLLLLRLLRRLLRRRLLRRRUDRLRRLLLLRRLRDURRRLLRRRLLRRLLRLLLLRRLLLRRLLRRLRDDRRRLLRRRLLRRLLRLDDLLLRRLLLRRLLRRLRRRRLLRRRLLRRLLRLUULLLRRLLLRRLLRRLRU
result:
ok Valid Solution (Length = 222).
Test #21:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
5 5 01010 10101 10101 11001 10011 4 1 5 4
output:
-1
result:
ok No Solution.
Test #22:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
5 5 10101 11111 10101 11111 11111 3 1 2 4
output:
UUDLRLRRUDDDRRRLLLRRRLLLLDLRLRRLRRULRRUUUDRLLRRDDDURLDRRLLRRRLLLRRRLLLLULRLRRUURRRLLLRRRLLLLDULRLRRDDRRRLLLRRRLLLLDLRLRRLRRULRRUURLLRUURRLURRLRRLRLDLLLLRRRLLLRRRDDRRLRLUDLLLLRRRLLLRRRUURRLRLULLLLRRRLLLRRRLLRRDLRUDDDRRLLRDUUURRLURRLRRLRLDLLLLRRRLLLRRRDDDURRLRLDUU
result:
ok Valid Solution (Length = 262).
Test #23:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
5 5 00001 11111 01110 01111 01111 1 5 5 2
output:
DLLLLLRDDDLRDUDDUULLRRDDLLLRRRDUDLDUDDUULDDLDUDDUUDDDUUULLRRLLLRRRLLLRRRRDUDLLLDDDDDDLLLDUDRRRRLLLRRRLLLRRLLUUUDDDUUDDUDLDDLUUDDUDLDUDRRRLLLDDRRLLUUDDUDRLDDDRLLLLLD
result:
ok Valid Solution (Length = 164).
Test #24:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
5 5 01011 10111 11011 10101 01110 4 1 2 3
output:
-1
result:
ok No Solution.
Test #25:
score: -100
Wrong Answer
time: 0ms
memory: 3740kb
input:
10 8 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 7 7 3 6
output:
UUUUUUU\x10\x10\x10\x10\x10\x10\x10DDUUUDDUUUDDUUUDDUUUDDUUURRLLRRRLLLRRRRLLLLRRRRRLLLLLRRRRRLLLLLLRRRRRLLLLLLRRRRRLLLLLLUUDDUUUDDDUUUUDDDDUUUUUDDDDDUUUUUUDDDDDDUUUUUUUDDDDDDDUUUUUUUDDDDDDDDUUUUUUUDDDDDDDDLRDUDDUURRRRRLLLLLLDDUUUDDUUUDDUUUDDUUUDDUUULLRRUUDDUUUDDDUUUUDDDDUUUUUDDDDDUUUUUUDDDDDDUUUUUUUDDDDDDDDDUUUUUUUUUUDD...
result:
wrong answer Line [name=User Output] equals to "UUUUUUU\x10\x10\x10\x10\x10\x10\x10DDUUUDDUUUDDUUUD...DDUUUDDUUUDDUUUDD\x10\x10\x10\x10\x10\x10\x10UUUUUUU", doesn't correspond to pattern "-1|[LRUD]{0,1000000}"