QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#403657#7751. Palindrome Pathucup-team3160#WA 1ms3620kbC++143.4kb2024-05-02 16:47:142024-05-02 16:47:16

Judging History

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

  • [2024-05-02 16:47:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3620kb
  • [2024-05-02 16:47:14]
  • 提交

answer

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf=1e18+5;
const ll mod=998244353;
const double eps=1e-15;
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline char getc()
{
    char ch=getchar();
    while(ch!='0'&&ch!='1'){ch=getchar();}
    return ch;
}
ll a[35][35];
char c[2000005],d[2000005];ll cntc,cntd;
ll vis[35][35][35][35];
ll flag[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char fla[4]={'D','U','R','L'};
bool ok;
void dfs(ll &sx,ll &sy,ll &tx,ll &ty,ll tox,ll toy)
{
    if(sx==tox&&sy==toy)
    {
        ok=1;return;
    }
    if(vis[sx][sy][tx][ty])return;
    vis[sx][sy][tx][ty]=1;
    ll fsx=sx,fsy=sy,ftx=tx,fty=ty;
    for(int i=0;i<4;i++)
    {   
        if(a[tx+flag[i][0]][ty+flag[i][1]]
        && !a[tx-flag[i][0]][ty-flag[i][1]])continue;
        if(!a[tx+flag[i][0]][ty+flag[i][1]])
        {
            if(a[sx+flag[i][0]][sy+flag[i][1]])sx+=flag[i][0],sy+=flag[i][1];
            c[++cntc]=fla[i];
            dfs(sx,sy,tx,ty,tox,toy);
            if(ok)return;
            cntc--;
            sx=fsx,sy=fsy,tx=ftx,ty=fty;
        }
        if(a[tx-flag[i][0]][ty-flag[i][1]])
        {
            tx-=flag[i][0],ty-=flag[i][1];
            if(a[sx+flag[i][0]][sy+flag[i][1]])sx+=flag[i][0],sy+=flag[i][1];
            c[++cntc]=fla[i];
            dfs(sx,sy,tx,ty,tox,toy);
            if(ok)return;
            cntc--;
            sx=fsx,sy=fsy,tx=ftx,ty=fty;
        }
    }
}
ll visx[35][35];
void dfsx(ll x,ll y)
{
    if(visx[x][y])return;
    visx[x][y]=1;
    for(int i=0;i<4;i++)
    {
        ll nx=x+flag[i][0],ny=y+flag[i][1];
        if(a[nx][ny]&&!visx[nx][ny])
        {
            d[++cntd]=fla[i];
            dfsx(nx,ny);
        }
    }
}
void solve()
{
    ll n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            a[i][j]=getc()-'0';
        }
    }
    ll sx=read(),sy=read(),tx=read(),ty=read();
    while(sx!=tx||sy!=ty)
    {
        ok=0;
        dfs(sx,sy,tx,ty,tx,ty);
        if(!ok){cout<<-1<<'\n';return;}
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
        {
            for(int p=1;p<=n;p++)for(int q=1;q<=m;q++)
            {
                vis[i][j][p][q]=0;
            }
        }
    }
    dfsx(sx,sy);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(a[i][j]&&(!visx[i][j])){cout<<-1<<'\n';return;}
        }
    }
    for(int i=1;i<=cntc;i++)cout<<c[i];
    for(int i=1;i<=cntd;i++)cout<<d[i];
    for(int i=1;i<=cntd;i++)
    {
        if(d[i]=='L')cout<<'R';
        if(d[i]=='R')cout<<'L';
        if(d[i]=='U')cout<<'D';
        if(d[i]=='D')cout<<'U';
    }
    for(int i=cntd;i>=1;i--)
    {
        if(d[i]=='L')cout<<'R';
        if(d[i]=='R')cout<<'L';
        if(d[i]=='U')cout<<'D';
        if(d[i]=='D')cout<<'U';
    }
    for(int i=cntd;i>=1;i--)cout<<d[i];
    for(int i=cntc;i>=1;i--)cout<<c[i];
    if(!cntc&&!cntd)cout<<'\n';
    return;
}
int main()
{
//    clock_t start=clock();
    ll t=1;
    while(t--)solve();
//    clock_t end=clock();
//    cout<<(end-start)*1.00/CLOCKS_PER_SEC<<'\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3548kb

input:

2 2
11
11
1 1 2 2

output:

DDURUDULDDRUURDDLUDURUDD

result:

ok Valid Solution (Length = 24).

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: 0ms
memory: 3560kb

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3556kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

DRUUUURDDDDLDDLDDUUULDDDDLUUUURUURUUDDDDUURUURUUUULDDDDLUUUDDLDDLDDDDRUUUURD

result:

wrong answer End Point Is (2,3), Not (er = 4, ec = 2)