QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#403689#7751. Palindrome Pathucup-team3160#WA 1ms3424kbC++143.3kb2024-05-02 17:25:472024-05-02 17:25:47

Judging History

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

  • [2024-05-02 17:25:47]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3424kb
  • [2024-05-02 17:25:47]
  • 提交

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)
{
    if(sx==tx&&sy==ty)
    {
        ok=1;return;
    }
    for(int i=0;i<4;i++)
    {
        if(sx+flag[i][0]==tx&&sy+flag[i][1]==ty)
        {
            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);
            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);
            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();
    dfs(sx,sy,tx,ty);
    if(!ok){cout<<-1<<'\n';return;}
    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<=cntd;i++)cout<<d[i];
    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=1;i<=cntc;i++)cout<<c[i];
    for(int i=cntc;i>=1;i--)cout<<c[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--)cout<<d[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;
}

详细

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3424kb

input:

2 2
11
11
1 1 2 2

output:

URDULDDDDLUDRU

result:

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