QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #395412 | #7751. Palindrome Path | linweitong | WA | 0ms | 3852kb | C++20 | 3.2kb | 2024-04-21 14:17:47 | 2024-04-21 14:17:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[35][35];
int sx,sy,ex,ey,b[100000][2],tot,tott,ckk;
bool vis[35][35];
const int dx[4]={0,0,-1,1};
const int dy[4]={1,-1,0,0};
void dfs(int x,int y){
b[++tot][0]=x,b[tot][1]=y;
vis[x][y]=1;
for (int i=0;i<4;++i){
int xx=x+dx[i],yy=y+dy[i];
if (xx<1||yy<1||xx>n||yy>m)continue;
if (a[xx][yy]==48)continue;
if (!vis[xx][yy]){
dfs(xx,yy);
b[++tot][0]=x,b[tot][1]=y;
}
}
}
void dfs2(int x,int y){
b[++tot][0]=x,b[tot][1]=y;
vis[x][y]=1;
if (x==ex&&y==ey){
tott=tot;
ckk=1;
return;
}
for (int i=0;i<4;++i){
int xx=x+dx[i],yy=y+dy[i];
if (xx<1||yy<1||xx>n||yy>m)continue;
if (a[xx][yy]==48)continue;
if (!vis[xx][yy]){
dfs2(xx,yy);
b[++tot][0]=x,b[tot][1]=y;
}
}
}
int tt[5];
char ttt[5]={'U','D','L','R'};
char anss[1000000];int ansl;
void gouzao(int tp,int x,int y){
for (int i=1;i<=x;++i)anss[++ansl]=ttt[tp];
for (int i=1;i<=y;++i)anss[++ansl]=ttt[tp^1];
// anss[++ansl]=' ';
}
void wk(int x,int y,int tp){
int s=0;
if (!tp){
for (int i=x-1;i>=1;--i){
if (a[i][y]==48)break;
++s;
}
}
else if (tp==1){
for (int i=x+1;i<=n;++i){
if (a[i][y]==48)break;
++s;
}
}
else if (tp==2){
for (int i=y-1;i>=1;--i){
if (a[x][i]==48)break;
++s;
}
}
else if (tp==3){
for (int i=y+1;i<=m;++i){
if (a[x][i]==48)break;
++s;
}
}
if (s<tt[tp]){
gouzao(tp,s+1,s+1);
}
else{
gouzao(tp,tt[tp],tt[tp]+1);
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i)scanf("%s",a[i]+1);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
for (int i=ex+1;i<=n;++i){
if (a[i][ey]==48){
break;
}
++tt[0];
}
for (int i=ex-1;i>=1;--i){
if (a[i][ey]==48){
break;
}
++tt[1];
}
for (int i=ey+1;i<=m;++i){
if (a[ex][i]==48){
break;
}
++tt[2];
}
for (int i=ey-1;i>=1;--i){
if (a[ex][i]==48){
break;
}
++tt[3];
}
dfs(sx,sy);
memset(vis,0,sizeof(vis));
dfs2(sx,sy);
if (!ckk){
return cout<<"-1\n",0;
}
tot=tott;
int nowx=sx,nowy=sy;
// cout<<nowx<<" "<<nowy<<"\n";
for (int i=2;i<=tot;++i){
// if (i==12){
// cout<<"!!!!\n";
// cout<<nowx<<" "<<nowy<<"\n";
// cout<<b[i][0]<<" "<<b[i][1]<<"\n";
// cout<<b[i][0]-nowx<<"|n";
// cout<<"!!!!\n";
// }
if (b[i][0]-nowx==1)wk(nowx,nowy,0);
if (nowx-b[i][0]==1)wk(nowx,nowy,1);
if (b[i][1]-nowy==1)wk(nowx,nowy,2);
if (nowy-b[i][1]==1)wk(nowx,nowy,3);
nowx=b[i][0],nowy=b[i][1];
// cout<<nowx<<" "<<nowy<<"\n";
}
// cout<<"\n";
for (int i=1;i<=ansl;++i)cout<<anss[i];
int u=sx,v=sy;
for (int i=1;i<=ansl;++i){
if (anss[i]=='U'&&u>1)--u;
if (anss[i]=='D'&&u<n)++u;
if (anss[i]=='L'&&v>1)--v;
if (anss[i]=='R'&&v<m)++v;
// cout<<u<<" "<<v<<"\n";
// if (anss[i]==' '){
// int ck=0;
// for (int j=i-1;j>=1;--j){
// if (anss[j]==' ')break;
// ck=j;
// }
// for (int j=ck;j<=i;++j)cout<<anss[j];
// cout<<"\n";
// }
}
for (int i=ansl;i>=1;--i)cout<<anss[i];
// for (int i=1;i<=tot;++i)a[b[i][0]][b[i][1]]=48;
// for (int i=1;i<=n;++i){
// for (int j=1;j<=m;++j){
// cout<<a[i][j];
// }
// cout<<"\n";
// }
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3848kb
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: 3640kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
LLRRLLRRRDDUURLRLLRLLDDDUUULRLLRRLLRRRDDDUUUURLRLLRLLLRLLRRLLRRRUDRLRLLRLLUDDUDDUDDLRLLRRLLRRRRLRLLRLLDUDDUULRLLRRLLRRRUDDRLRLLLLRLRDDURRRLLRRLLRLUUDDUDLLRLLRLRRRRLLRRLLRLDDUDDUDDULLRLLRLRDURRRLLRRLLRLLLRLLRLRUUUUDDDRRRLLRRLLRLUUUDDDLLRLLRLRUUDDRRRLLRRLL
result:
ok Valid Solution (Length = 254).
Test #5:
score: 0
Accepted
time: 0ms
memory: 3652kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
RDDRLRRLLRRRLLLRRRRLLLLDDDUUUDDDDUUUURRDDDDDUUUURRRLLLRRRRLLLLDDDDRRRRDUDRLRRLLDUDRRRLLLRRRRLLLLDUDDUURRRRDDDUUUDDDDUUUURLRDDRLRRLLRRRLLLRRRRLLLLDDDUUUDDDDUUUURRDDDDDUUUURRRLLLRRRRLLLLDDDDRRRRRRRRDDDDLLLLRRRRLLLRRRUUUUDDDDDRRUUUUDDDDUUUDDDLLLLRRRRLLLRRRLLRRLRDDRLRUUUUDDDDUUUDDDRRRRUUDDUDLLLLRRRRLLLR...
result:
ok Valid Solution (Length = 384).
Test #6:
score: 0
Accepted
time: 0ms
memory: 3840kb
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: 3728kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
LUUDUUDDRRRUUUDUUDDUUDDDLUUDDURULLLURLUULRULLLURUDDUULDDDUUDDUUDUUURRRDDUUDUUL
result:
ok Valid Solution (Length = 78).
Test #8:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
LRLRRRLRLLUULRLRRUDRLRLLUDDDDULRLRRRLRLLUULRRLUULLRLRRRLRLUDDDDULLRLRDURRLRLUULLRLRRRLRL
result:
ok Valid Solution (Length = 88).
Test #9:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
5 5 01110 10110 11110 11011 11100 2 4 5 1
output:
LDDUULLRRLLLRDDLLRRRDLRLDULLLDDDUUUDDLRDLLRRLLLRDULDDUULRLLRRDULRLDDUULLRRLLLRDDLLRRRDLRLDULLLDDDUUUDDLRDLLRRLLLLRRLLDRLDDUUUDDDLLLUDLRLDRRRLLDDRLLLRRLLUUDDLRLUDRRLLRLUUDDLUDRLLLRRLLDRLDDUUUDDDLLLUDLRLDRRRLLDDRLLLRRLLUUDDL
result:
ok Valid Solution (Length = 222).
Test #10:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
5 3 011 111 110 111 011 3 1 2 1
output:
LRULLRRULLRUDLLLRUUDDUUDDDLLRRUDLLRULLLRULLRULLRRULLRUDLLLLDURLLURRLLURLLURLLLURLLDURRLLDDDUUDDUURLLLDURLLURRLLURL
result:
ok Valid Solution (Length = 114).
Test #11:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
4 5 11111 11111 11111 11111 3 2 1 3
output:
LLRRLLRRRLLRRRURLRRLLRRLLLRRLLLULRLLRRLLRRRLLRRRRLRRLLRRLLLRRLLLUDUUDDUUUDDDLRLLRRLLRRRLLRRRRLRRLLRRLLLRRLLLUULRLLRRLLRRRLLRRRUUDDRLRRLLRRLLLLLRRLLRRRLLRRRURLRRLLRRLLLRRLLLULRLLRRRRLLRLULLLRRLLLRRLLRRLRURRRLLRRRLLRRLLLLLRRLLRRLRDDUURRRLLRRRLLRRLLRLUULLLRRLLLRRLLRRLRRRRLLRRRLLRRLLRLDDDUUUDDUUDULLLRRL...
result:
ok Valid Solution (Length = 358).
Test #12:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
5 5 11111 10101 11111 10101 11111 2 5 1 1
output:
ULLLLUDUUDDLRLLRRLLLRRRLLLLRRRRUUUDDDUUUUDDDDLLLLUUUUUDDDDLRLLRRUUUUUDDDDLLLRRRLLLLRRRRUULLUUUDDLLUULRLLRRLLLRRRLLLLRRRRUDULLLLLLLLUDURRRRLLLLRRRLLLRRLLRLUULLDDUUULLUURRRRLLLLRRRLLLDDDDUUUUURRLLRLDDDDUUUUULLLLDDDDUUUUDDDUUURRRRLLLLRRRLLLRRLLRLDDUUDULLLLU
result:
ok Valid Solution (Length = 254).
Test #13:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
4 5 11111 10000 11111 00001 1 3 4 5
output:
RRLLLLDDRRRRDDULLLLDUDUURRRRLLLLDDRRRRDDRRRRDDLLLLRRRRUUDUDLLLLUDDRRRRDDLLLLRR
result:
ok Valid Solution (Length = 78).
Test #14:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
3 5 10100 00010 00111 1 3 1 1
output:
-1
result:
ok No Solution.
Test #15:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
4 5 10001 11111 11100 11111 4 5 3 1
output:
LLLLDULRLLRRDDUULLRRRLLRRRDUUDLLLLDDUUUUDLRLLRRUDLLUDDLRLLRRLLRRRLLRRRLLLLDUUDLLLLRRRLLRRRLLRRLLRLDDULLDURRLLRLDUUUUDDLLLLDUUDRRRLLRRRLLUUDDRRLLRLUDLLLL
result:
ok Valid Solution (Length = 152).
Test #16:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
3 5 11111 10100 11111 1 2 3 5
output:
RRRRLRRLLDDRRRLRRLLRRRLLLRRRRLLLLUUDDRRUURRRLLLRRRRLRRLLDDRRRRDDLLRRLRRRRLLLRRRUURRDDUULLLLRRRRLLLRRRLLRRLRRRDDLLRRLRRRR
result:
ok Valid Solution (Length = 120).
Test #17:
score: -100
Wrong Answer
time: 0ms
memory: 3852kb
input:
4 5 01110 10101 11011 10111 1 3 2 3
output:
RLLRDDURLLRDDRLLRUDDRLLR
result:
wrong answer (2,1) Not Visited