QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#394454#7751. Palindrome PathtanxiWA 1ms3764kbC++143.5kb2024-04-20 14:52:452024-04-20 14:52:45

Judging History

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

  • [2024-04-20 14:52:45]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3764kb
  • [2024-04-20 14:52:45]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char ch[4]={'R','L','D','U'};
int f[39][39][4];
int a[39][39],vis[39][39];
pair<int,int>stk[N];
int top,n,m;
void dfs(int x,int y)
{
    vis[x][y]=1;
    stk[++top]={x,y};
    for(int t=0;t<4;t++)
    {
        int nx=x+dx[t];
        int ny=y+dy[t];
        if(!a[nx][ny])
        continue;
        if(vis[nx][ny])
        continue;
        dfs(nx,ny);
        stk[++top]={x,y};
    }
}
int stx,sty,edx,edy;
string s;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen("er.err","w",stderr);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char c;
            cin>>c;
            a[i][j]=c-'0';
        }
    }
    cin>>stx>>sty>>edx>>edy;
    memset(f,-1,sizeof(f));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(!a[i][j])
            {
                f[i][j][3]=f[i][j][1]=-1;
            }
            else
            {
                f[i][j][3]=f[i-1][j][3]+1;
                f[i][j][1]=f[i][j-1][1]+1;
            }
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=n;j>=1;j--)
        {
            if(!a[i][j])
            {
                f[i][j][2]=f[i][j][0]=-1;
            }
            else
            {
                f[i][j][2]=f[i+1][j][2]+1;
                f[i][j][0]=f[i][j+1][0]+1;
            }
        }
    }
    dfs(stx,sty);
    if(!vis[edx][edy])
    {
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=top;i++)
    {
        stk[++top]=stk[i];
        if(stk[i].first==edx&&stk[i].second==edy)
        break;
    }
    for(int i=1;i<top;i++)
    {
        int x=stk[i].first,y=stk[i].second;
        for(int t=0;t<4;t++)
        {
            if(stk[i+1].first==x+dx[t]&&stk[i+1].second==y+dy[t])
            {
                // cerr<<x<<','<<y<<"to"<<stk[i+1].first<<','<<stk[i+1].second<<'\n';
                int k=f[x][y][t^1];
                int p=f[edx][edy][t];
                if(k==p)
                {
                    for(int j=1;j<=k;j++)
                    {
                        s+=ch[t^1];
                        // cerr<<ch[t^1];
                    }
                    for(int j=1;j<=k+1;j++)
                    {
                        s+=ch[t];
                        // cerr<<ch[t];
                    }
                }
                else
                if(k>p)
                {
                    for(int j=1;j<=p;j++)
                    {
                        s+=ch[t^1];
                        // cerr<<ch[t^1];
                    }
                    for(int j=1;j<=p+1;j++)
                    {
                        s+=ch[t];
                        // cerr<<ch[t];
                    }
                }
                else
                {
                    for(int j=1;j<=k+1;j++)
                    {
                        s+=ch[t^1];
                        // cerr<<ch[t^1];
                    }
                    for(int j=1;j<=k+1;j++)
                    {
                        s+=ch[t];
                        // cerr<<ch[t];
                    }
                }
                // cerr<<'\n';
                break;
            }
        }
    }
    cout<<s;
    reverse(s.begin(),s.end());
    cout<<s;
    return 0;
}

详细

Test #1:

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

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: 3620kb

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: 0
Accepted
time: 1ms
memory: 3668kb

input:

1 1
1
1 1 1 1

output:


result:

ok Valid Solution (Length = 0).

Test #4:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

LLRRLLRRRUDDRLRLLRLLDUDDUULRLLRRLLRRRDDDUUURLRLLRLLDDDUUUULRLLRRLLRRRRLRLLRLLUDLRLLRRLLRRRUDDRLRLLRLLUDDUDDLRLLRRLLRRRDURLRLLLLRLRUDRRRLLRRLLRLDDUDDULLRLLRLRDDURRRLLRRLLRLDULLRLLRLRRRRLLRRLLRLUUUUDDDLLRLLRLRUUUDDDRRRLLRRLLRLUUDDUDLLRLLRLRDDURRRLLRRLL

result:

ok Valid Solution (Length = 250).

Test #5:

score: 0
Accepted
time: 0ms
memory: 3672kb

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

RDDRLRRLLRRRLLLRRRRLLLLDDRRRRDUDRLRRLLDUDRRRLLLRRRRLLLLDUDDUUDDDUUUDDDDUUUURRDDDDDUUUURRRLLLRRRRLLLLDDRRRRDDDUUUDDDDUUUURLRDDRLRRLLRRRLLLRRRRLLLLDDRRRRRRRRDDLLLLRRRRLLLRRRLLRRLRDDRLRUUUUDDDDUUUDDDRRRRDDLLLLRRRRLLLRRRUUUUDDDDDRRUUUUDDDDUUUDDDUUDDUDLLLLRRRRLLLRRRDUDLLRRLRDUDRRRRDDLLLLRRRRLLLRRRLLRRLRDDR

result:

ok Valid Solution (Length = 302).

Test #6:

score: 0
Accepted
time: 1ms
memory: 3680kb

input:

5 3
111
100
111
001
111
4 3 3 2

output:

DRLRLLLRLRRUURLRLLUULRLRRRLRLLDDLRLRRDDRLRLLLRLRRUURLLRUURRLRLLLRLRDDRRLRLDDLLRLRRRLRLUULLRLRUURRLRLLLRLRD

result:

ok Valid Solution (Length = 106).

Test #7:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

LUUDDRRRUUDDDLUUDDURUUUUDUUDDLLLUUUDRLUUDDRRRUUDDDLUUDDURUUUUDUUDDLLLUUUULLLDDUUDUUUURUDDUULDDDUURRRDDUULRDUUULLLDDUUDUUUURUDDUULDDDUURRRDDUUL

result:

ok Valid Solution (Length = 142).

Test #8:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

5 3
101
111
100
111
100
4 1 2 2

output:

LRLRRRLRLLDUUULRLRRUDRLRLLUDDDLRLRRRLRLLDUUULRRLUUUDLLRLRRRLRLDDDULLRLRDURRLRLUUUDLLRLRRRLRL

result:

ok Valid Solution (Length = 92).

Test #9:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

5 5
01110
10110
11110
11011
11100
2 4 5 1

output:

LDLLRRRDLRLDULLLDLRDLLRRLLLRDULDDUUDDDUUUDLRLLRRDUDDUULLRRLLLRDLRLDLLRRRDLRLDULLLDLRDLLRRLLLLRRLLDRLDLLLUDLRLDRRRLLDLRLDRLLLRRLLUUDDUDRRLLRLDUUUDDDUUDDLUDRLLLRRLLDRLDLLLUDLRLDRRRLLDL

result:

ok Valid Solution (Length = 182).

Test #10:

score: 0
Accepted
time: 0ms
memory: 3680kb

input:

5 3
011
111
110
111
011
3 1 2 1

output:

LRUUDDDLLRRUDLLRULLLRUULLRRULLRUDLLLRUUDDLLRUUDDDLLRRUDLLRULLLRUULLRRULLRUDLLLLDURLLURRLLUURLLLURLLDURRLLDDDUURLLDDUURLLLDURLLURRLLUURLLLURLLDURRLLDDDUURL

result:

ok Valid Solution (Length = 154).

Test #11:

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

input:

4 5
11111
11111
11111
11111
3 2 1 3

output:

LRRLRRLRRRLRRLLRRLLLUULRLRRLRRLRRRLRRLLRRLLLLRLRRLRRLRRRLRRLLRRLLLUUDDUUUDDDLRLRRLRRLRRRLRRLLLRRLRRLRRRLRRLLRRLLLUULRLRRLRRLRRRLLRRRLRRLRRLRLUULLLRRLLRRLRRRLRRLRRLLLRRLRRRLRRLRRLRLDDDUUUDDUULLLRRLLRRLRRRLRRLRRLRLLLLRRLLRRLRRRLRRLRRLRLUULLLRRLLRRLRRRLRRLRRL

result:

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