QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394191 | #7751. Palindrome Path | NATURAL6 | WA | 0ms | 3856kb | C++14 | 1.6kb | 2024-04-20 10:00:24 | 2024-04-20 10:00:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int qread()
{
int a=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){(a*=10)+=(ch^48);ch=getchar();}
return a*f;
}
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
char dir[5]="RDLU";
int n,m,cnt,Sx,Sy,Tx,Ty,vis[40][40];
char ch[40][40];
inline bool check(int x,int y){return 1<=x&&x<=n&&1<=y&&y<=m&&ch[x][y]=='1';}
vector<int>pa;
string Ans;
inline void to(int x,int y,int k)
{
int X=Tx,Y=Ty,fk=k^2,len=0;
while(check(x+dx[fk],y+dy[fk])&&check(X+dx[k],Y+dy[k]))
{
x+=dx[fk],y+=dy[fk];
X+=dx[k],Y+=dx[k];
Ans+=dir[fk];
++len;
}
if(!check(x+dx[fk],y+dy[fk])&&check(X+dx[k],Y+dy[k]))Ans+=dir[fk];
for(int i=1;i<=len+1;++i)Ans+=dir[k];
cerr<<Ans<<endl;
return ;
}
inline void dfs(int X,int Y)
{
if(!vis[X][Y])vis[X][Y]=1,--cnt;
for(int k=0,x,y;k<=3;++k)
{
x=X+dx[k],y=Y+dy[k];
if(!check(x,y))continue;
if(vis[x][y])continue;
to(X,Y,k);
if(!vis[Tx][Ty])pa.emplace_back(k);
dfs(x,y);
to(x,y,k^2);
if(!vis[Tx][Ty])pa.pop_back();
}
return ;
}
int main()
{
n=qread(),m=qread();
for(int i=1;i<=n;++i)
{
scanf("%s",ch[i]+1);
for(int j=1;j<=m;++j)cnt+=(ch[i][j]=='1');
}
Sx=qread(),Sy=qread(),Tx=qread(),Ty=qread();
dfs(Sx,Sy);
if(cnt)return puts("-1"),0;
for(int i:pa)
{
to(Sx,Sy,i);
Sx+=dx[i];Sy+=dy[i];
}
cout<<Ans;
reverse(Ans.begin(),Ans.end());
cout<<Ans;
return 0;
}
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: 3856kb
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: -100
Wrong Answer
time: 0ms
memory: 3672kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
LLRRLLLRRRUDDRLRRLLRRRLLLDUDDUULRLLRRLLLRRRDDUUURLRRLLRRRLLLDDUUULRLLRRLLLRRRRLRRLLRRRLLLUDLRLLRRLLLRRRUDDRLRRLLRRRLLLUDDUDDLRLLRRLLLRRRDURLRRLLLLRRLRUDRRRLLLRRLLRLDDUDDULLLRRRLLRRLRDDURRRLLLRRLLRLDULLLRRRLLRRLRRRRLLLRRLLRLUUUDDLLLRRRLLRRLRUUUDDRRRLLLRRLLRLUUDDUDLLLRRRLLRRLRDDURRRLLLRRLL
result:
wrong answer End Point Is (4,1), Not (er = 4, ec = 2)