QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394890 | #7751. Palindrome Path | linweitong | WA | 1ms | 3848kb | C++20 | 2.3kb | 2024-04-20 21:22:16 | 2024-04-20 21:22:17 |
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];
}
void wk(int x,int y,int tp){
int s=0;
if (!tp){
for (int i=x-1;i>=1;--i){
if (a[i][ey]==48)break;
++s;
}
}
else if (tp==1){
for (int i=x+1;i<=n;++i){
if (a[i][ey]==48)break;
++s;
}
}
else if (tp==2){
for (int i=y-1;i>=1;--i){
if (a[ex][i]==48)break;
++s;
}
}
else if (tp==3){
for (int i=y+1;i<=m;++i){
if (a[ex][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;
for (int i=2;i<=tot;++i){
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];
}
for (int i=1;i<=ansl;++i)cout<<anss[i];
for (int i=ansl;i>=1;--i)cout<<anss[i];
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3732kb
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: 3840kb
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: 3848kb
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: 1ms
memory: 3760kb
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: 3844kb
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: 3768kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
LUUDUUDDRRRUUUDUUDDUUDDDLUUDDDURULLLURLUULRULLLURUDDDUULDDDUUDDUUDUUURRRDDUUDUUL
result:
ok Valid Solution (Length = 80).
Test #8:
score: 0
Accepted
time: 0ms
memory: 3836kb
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: 3712kb
input:
5 5 01110 10110 11110 11011 11100 2 4 5 1
output:
LDDDUUUULLRRRLLLLRRDDLLRRRDLLRRRLDDUULLLDDDUUUDDLRDLLRRLLLRDULDDUULRLLRRDDDUUULLRRRLDDDUUUULLRRRLLLLRRDDLLRRRDLLRRRLDDUULLLDDDUUUDDLRDLLRRLLLLRRLLDRLDDUUUDDDLLLUUDDLRRRLLDRRRLLDDRRLLLLRRRLLUUUUDDDLRRRLLUUUDDDRRLLRLUUDDLUDRLLLRRLLDRLDDUUUDDDLLLUUDDLRRRLLDRRRLLDDRRLLLLRRRLLUUUUDDDL
result:
ok Valid Solution (Length = 280).
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3648kb
input:
5 3 011 111 110 111 011 3 1 2 1
output:
LRULLRRULLLRRUDLLLRUDUUDDLLRRUUDDDLLLRRULLLRULLRULLRRULLLRRUDLLLLDURRLLLURRLLURLLURLLLURRLLLDDDUURRLLDDUUDURLLLDURRLLLURRLLURL
result:
wrong answer (5,2) Not Visited