QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #394440 | #7751. Palindrome Path | tanxi | WA | 0ms | 3764kb | C++14 | 2.8kb | 2024-04-20 14:47:05 | 2024-04-20 14:47:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char ch[4]={'R','L','D','U'};
int f[39][39][4];
int a[39][39],vis[39][39];
pair<int,int>stk[N];
int top,n,m;
void dfs(int x,int y)
{
vis[x][y]=1;
stk[++top]={x,y};
for(int t=0;t<4;t++)
{
int nx=x+dx[t];
int ny=y+dy[t];
if(!a[nx][ny])
continue;
if(vis[nx][ny])
continue;
dfs(nx,ny);
stk[++top]={x,y};
}
}
int stx,sty,edx,edy;
string s;
signed 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 c;
cin>>c;
a[i][j]=c-'0';
}
}
cin>>stx>>sty>>edx>>edy;
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(!a[i][j])
{
f[i][j][3]=f[i][j][1]=-1;
}
else
{
f[i][j][3]=f[i-1][j][3]+1;
f[i][j][1]=f[i][j-1][1]+1;
}
}
}
for(int i=n;i>=1;i--)
{
for(int j=n;j>=1;j--)
{
if(!a[i][j])
{
f[i][j][2]=f[i][j][0]=-1;
}
else
{
f[i][j][2]=f[i+1][j][2]+1;
f[i][j][0]=f[i][j+1][0]+1;
}
}
}
dfs(stx,sty);
if(!vis[edx][edy])
{
cout<<-1;
return 0;
}
for(int i=1;i<=top;i++)
{
stk[++top]=stk[i];
if(stk[i].first==edx&&stk[i].second==edy)
break;
}
for(int i=2;i<top;i++)
{
int x=stk[i].first,y=stk[i].second;
for(int t=0;t<4;t++)
{
if(stk[i+1].first==x+dx[t]&&stk[i+1].second==y+dy[t])
{
int k=f[x][y][t^1];
int p=f[edx][edy][t];
if(k==p)
{
for(int j=1;j<=k;j++)
s+=ch[t^1];
for(int j=1;j<=k+1;j++)
s+=ch[t];
}
else
if(k>p)
{
for(int j=1;j<=p;j++)
s+=ch[t^1];
for(int j=1;j<=p+1;j++)
s+=ch[t];
}
else
{
for(int j=1;j<=k+1;j++)
s+=ch[t^1];
for(int j=1;j<=k+1;j++)
s+=ch[t];
}
break;
}
}
}
cout<<s;
reverse(s.begin(),s.end());
cout<<s;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3728kb
input:
2 2 11 11 1 1 2 2
output:
DRLRDURLRDDRLRUDRLRD
result:
ok Valid Solution (Length = 20).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3732kb
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:
LLRRRUDDRLRLLRLLDUDDUULRLLRRLLRRRDDDUUURLRLLRLLDDDUUUULRLLRRLLRRRRLRLLRLLUDLRLLRRLLRRRUDDRLRLLRLLUDDUDDLRLLRRLLRRRDURLRLLLLRLRUDRRRLLRRLLRLDDUDDULLRLLRLRDDURRRLLRRLLRLDULLRLLRLRRRRLLRRLLRLUUUUDDDLLRLLRLRUUUDDDRRRLLRRLLRLUUDDUDLLRLLRLRDDURRRLL
result:
ok Valid Solution (Length = 242).
Test #5:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
DDRLRRLLRRRLLLRRRRLLLLDDRRRRDUDRLRRLLDUDRRRLLLRRRRLLLLDUDDUUDDDUUUDDDDUUUURRDDDDDUUUURRRLLLRRRRLLLLDDRRRRDDDUUUDDDDUUUURLRDDRLRRLLRRRLLLRRRRLLLLDDRRRRRRRRDDLLLLRRRRLLLRRRLLRRLRDDRLRUUUUDDDDUUUDDDRRRRDDLLLLRRRRLLLRRRUUUUDDDDDRRUUUUDDDDUUUDDDUUDDUDLLLLRRRRLLLRRRDUDLLRRLRDUDRRRRDDLLLLRRRRLLLRRRLLRRLRDD
result:
ok Valid Solution (Length = 300).
Test #6:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
5 3 111 100 111 001 111 4 3 3 2
output:
RLRLLLRLRRUURLRLLUULRLRRRLRLLDDLRLRRDDRLRLLLRLRRUURLLRUURRLRLLLRLRDDRRLRLDDLLRLRRRLRLUULLRLRUURRLRLLLRLR
result:
ok Valid Solution (Length = 104).
Test #7:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
UUDDRRRUUDDDLUUDDURUUUUDUUDDLLLUUUDRLUUDDRRRUUDDDLUUDDURUUUUDUUDDLLLUUUULLLDDUUDUUUURUDDUULDDDUURRRDDUULRDUUULLLDDUUDUUUURUDDUULDDDUURRRDDUU
result:
ok Valid Solution (Length = 140).
Test #8:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
LRRRLRLLDUUULRLRRUDRLRLLUDDDLRLRRRLRLLDUUULRRLUUUDLLRLRRRLRLDDDULLRLRDURRLRLUUUDLLRLRRRL
result:
ok Valid Solution (Length = 88).
Test #9:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5 5 01110 10110 11110 11011 11100 2 4 5 1
output:
DLLRRRDLRLDULLLDLRDLLRRLLLRDULDDUUDDDUUUDLRLLRRDUDDUULLRRLLLRDLRLDLLRRRDLRLDULLLDLRDLLRRLLLLRRLLDRLDLLLUDLRLDRRRLLDLRLDRLLLRRLLUUDDUDRRLLRLDUUUDDDUUDDLUDRLLLRRLLDRLDLLLUDLRLDRRRLLD
result:
ok Valid Solution (Length = 180).
Test #10:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
5 3 011 111 110 111 011 3 1 2 1
output:
UUDDDLLRRUDLLRULLLRUULLRRULLRUDLLLRUUDDLLRUUDDDLLRRUDLLRULLLRUULLRRULLRUDLLLLDURLLURRLLUURLLLURLLDURRLLDDDUURLLDDUURLLLDURLLURRLLUURLLLURLLDURRLLDDDUU
result:
ok Valid Solution (Length = 150).
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3764kb
input:
4 5 11111 11111 11111 11111 3 2 1 3
output:
LRRLRRRLRRLLRRLLLUULRLRRLRRLRRRLRRLLRRLLLLRLRRLRRLRRRLRRLLRRLLLUUDDUUUDDDLRLRRLRRLRRRLRRLLLRRLRRLRRRLRRLLRRLLLUULRLRRLRRLRRRLLRRRLRRLRRLRLUULLLRRLLRRLRRRLRRLRRLLLRRLRRRLRRLRRLRLDDDUUUDDUULLLRRLLRRLRRRLRRLRRLRLLLLRRLLRRLRRRLRRLRRLRLUULLLRRLLRRLRRRLRRL
result:
wrong answer End Point Is (1,4), Not (er = 1, ec = 3)