QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394191#7751. Palindrome PathNATURAL6WA 0ms3856kbC++141.6kb2024-04-20 10:00:242024-04-20 10:00:24

Judging History

你现在查看的是最新测评结果

  • [2024-04-20 10:00:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3856kb
  • [2024-04-20 10:00:24]
  • 提交

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)