QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #394454 | #7751. Palindrome Path | tanxi | WA | 1ms | 3764kb | C++14 | 3.5kb | 2024-04-20 14:52:45 | 2024-04-20 14:52:45 |
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);
// freopen("er.err","w",stderr);
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=1;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])
{
// cerr<<x<<','<<y<<"to"<<stk[i+1].first<<','<<stk[i+1].second<<'\n';
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];
// cerr<<ch[t^1];
}
for(int j=1;j<=k+1;j++)
{
s+=ch[t];
// cerr<<ch[t];
}
}
else
if(k>p)
{
for(int j=1;j<=p;j++)
{
s+=ch[t^1];
// cerr<<ch[t^1];
}
for(int j=1;j<=p+1;j++)
{
s+=ch[t];
// cerr<<ch[t];
}
}
else
{
for(int j=1;j<=k+1;j++)
{
s+=ch[t^1];
// cerr<<ch[t^1];
}
for(int j=1;j<=k+1;j++)
{
s+=ch[t];
// cerr<<ch[t];
}
}
// cerr<<'\n';
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: 1ms
memory: 3736kb
input:
2 2 11 11 1 1 2 2
output:
RDRLRDURLRDDRLRUDRLRDR
result:
ok Valid Solution (Length = 22).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3668kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
LLRRLLRRRUDDRLRLLRLLDUDDUULRLLRRLLRRRDDDUUURLRLLRLLDDDUUUULRLLRRLLRRRRLRLLRLLUDLRLLRRLLRRRUDDRLRLLRLLUDDUDDLRLLRRLLRRRDURLRLLLLRLRUDRRRLLRRLLRLDDUDDULLRLLRLRDDURRRLLRRLLRLDULLRLLRLRRRRLLRRLLRLUUUUDDDLLRLLRLRUUUDDDRRRLLRRLLRLUUDDUDLLRLLRLRDDURRRLLRRLL
result:
ok Valid Solution (Length = 250).
Test #5:
score: 0
Accepted
time: 0ms
memory: 3672kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
RDDRLRRLLRRRLLLRRRRLLLLDDRRRRDUDRLRRLLDUDRRRLLLRRRRLLLLDUDDUUDDDUUUDDDDUUUURRDDDDDUUUURRRLLLRRRRLLLLDDRRRRDDDUUUDDDDUUUURLRDDRLRRLLRRRLLLRRRRLLLLDDRRRRRRRRDDLLLLRRRRLLLRRRLLRRLRDDRLRUUUUDDDDUUUDDDRRRRDDLLLLRRRRLLLRRRUUUUDDDDDRRUUUUDDDDUUUDDDUUDDUDLLLLRRRRLLLRRRDUDLLRRLRDUDRRRRDDLLLLRRRRLLLRRRLLRRLRDDR
result:
ok Valid Solution (Length = 302).
Test #6:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
5 3 111 100 111 001 111 4 3 3 2
output:
DRLRLLLRLRRUURLRLLUULRLRRRLRLLDDLRLRRDDRLRLLLRLRRUURLLRUURRLRLLLRLRDDRRLRLDDLLRLRRRLRLUULLRLRUURRLRLLLRLRD
result:
ok Valid Solution (Length = 106).
Test #7:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
LUUDDRRRUUDDDLUUDDURUUUUDUUDDLLLUUUDRLUUDDRRRUUDDDLUUDDURUUUUDUUDDLLLUUUULLLDDUUDUUUURUDDUULDDDUURRRDDUULRDUUULLLDDUUDUUUURUDDUULDDDUURRRDDUUL
result:
ok Valid Solution (Length = 142).
Test #8:
score: 0
Accepted
time: 0ms
memory: 3684kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
LRLRRRLRLLDUUULRLRRUDRLRLLUDDDLRLRRRLRLLDUUULRRLUUUDLLRLRRRLRLDDDULLRLRDURRLRLUUUDLLRLRRRLRL
result:
ok Valid Solution (Length = 92).
Test #9:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
5 5 01110 10110 11110 11011 11100 2 4 5 1
output:
LDLLRRRDLRLDULLLDLRDLLRRLLLRDULDDUUDDDUUUDLRLLRRDUDDUULLRRLLLRDLRLDLLRRRDLRLDULLLDLRDLLRRLLLLRRLLDRLDLLLUDLRLDRRRLLDLRLDRLLLRRLLUUDDUDRRLLRLDUUUDDDUUDDLUDRLLLRRLLDRLDLLLUDLRLDRRRLLDL
result:
ok Valid Solution (Length = 182).
Test #10:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
5 3 011 111 110 111 011 3 1 2 1
output:
LRUUDDDLLRRUDLLRULLLRUULLRRULLRUDLLLRUUDDLLRUUDDDLLRRUDLLRULLLRUULLRRULLRUDLLLLDURLLURRLLUURLLLURLLDURRLLDDDUURLLDDUURLLLDURLLURRLLUURLLLURLLDURRLLDDDUURL
result:
ok Valid Solution (Length = 154).
Test #11:
score: -100
Wrong Answer
time: 0ms
memory: 3740kb
input:
4 5 11111 11111 11111 11111 3 2 1 3
output:
LRRLRRLRRRLRRLLRRLLLUULRLRRLRRLRRRLRRLLRRLLLLRLRRLRRLRRRLRRLLRRLLLUUDDUUUDDDLRLRRLRRLRRRLRRLLLRRLRRLRRRLRRLLRRLLLUULRLRRLRRLRRRLLRRRLRRLRRLRLUULLLRRLLRRLRRRLRRLRRLLLRRLRRRLRRLRRLRLDDDUUUDDUULLLRRLLRRLRRRLRRLRRLRLLLLRRLLRRLRRRLRRLRRLRLUULLLRRLLRRLRRRLRRLRRL
result:
wrong answer End Point Is (1,4), Not (er = 1, ec = 3)