QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#394440#7751. Palindrome PathtanxiWA 0ms3764kbC++142.8kb2024-04-20 14:47:052024-04-20 14:47:05

Judging History

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

  • [2024-04-20 14:47:05]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3764kb
  • [2024-04-20 14:47:05]
  • 提交

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);
    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=2;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])
            {
                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];
                    for(int j=1;j<=k+1;j++)
                    s+=ch[t];
                }
                else
                if(k>p)
                {
                    for(int j=1;j<=p;j++)
                    s+=ch[t^1];
                    for(int j=1;j<=p+1;j++)
                    s+=ch[t];
                }
                else
                {
                    for(int j=1;j<=k+1;j++)
                    s+=ch[t^1];
                    for(int j=1;j<=k+1;j++)
                    s+=ch[t];
                }
                break;
            }
        }
    }
    cout<<s;
    reverse(s.begin(),s.end());
    cout<<s;
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3728kb

input:

2 2
11
11
1 1 2 2

output:

DRLRDURLRDDRLRUDRLRD

result:

ok Valid Solution (Length = 20).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:


result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

LLRRRUDDRLRLLRLLDUDDUULRLLRRLLRRRDDDUUURLRLLRLLDDDUUUULRLLRRLLRRRRLRLLRLLUDLRLLRRLLRRRUDDRLRLLRLLUDDUDDLRLLRRLLRRRDURLRLLLLRLRUDRRRLLRRLLRLDDUDDULLRLLRLRDDURRRLLRRLLRLDULLRLLRLRRRRLLRRLLRLUUUUDDDLLRLLRLRUUUDDDRRRLLRRLLRLUUDDUDLLRLLRLRDDURRRLL

result:

ok Valid Solution (Length = 242).

Test #5:

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

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

DDRLRRLLRRRLLLRRRRLLLLDDRRRRDUDRLRRLLDUDRRRLLLRRRRLLLLDUDDUUDDDUUUDDDDUUUURRDDDDDUUUURRRLLLRRRRLLLLDDRRRRDDDUUUDDDDUUUURLRDDRLRRLLRRRLLLRRRRLLLLDDRRRRRRRRDDLLLLRRRRLLLRRRLLRRLRDDRLRUUUUDDDDUUUDDDRRRRDDLLLLRRRRLLLRRRUUUUDDDDDRRUUUUDDDDUUUDDDUUDDUDLLLLRRRRLLLRRRDUDLLRRLRDUDRRRRDDLLLLRRRRLLLRRRLLRRLRDD

result:

ok Valid Solution (Length = 300).

Test #6:

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

input:

5 3
111
100
111
001
111
4 3 3 2

output:

RLRLLLRLRRUURLRLLUULRLRRRLRLLDDLRLRRDDRLRLLLRLRRUURLLRUURRLRLLLRLRDDRRLRLDDLLRLRRRLRLUULLRLRUURRLRLLLRLR

result:

ok Valid Solution (Length = 104).

Test #7:

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

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

UUDDRRRUUDDDLUUDDURUUUUDUUDDLLLUUUDRLUUDDRRRUUDDDLUUDDURUUUUDUUDDLLLUUUULLLDDUUDUUUURUDDUULDDDUURRRDDUULRDUUULLLDDUUDUUUURUDDUULDDDUURRRDDUU

result:

ok Valid Solution (Length = 140).

Test #8:

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

input:

5 3
101
111
100
111
100
4 1 2 2

output:

LRRRLRLLDUUULRLRRUDRLRLLUDDDLRLRRRLRLLDUUULRRLUUUDLLRLRRRLRLDDDULLRLRDURRLRLUUUDLLRLRRRL

result:

ok Valid Solution (Length = 88).

Test #9:

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

input:

5 5
01110
10110
11110
11011
11100
2 4 5 1

output:

DLLRRRDLRLDULLLDLRDLLRRLLLRDULDDUUDDDUUUDLRLLRRDUDDUULLRRLLLRDLRLDLLRRRDLRLDULLLDLRDLLRRLLLLRRLLDRLDLLLUDLRLDRRRLLDLRLDRLLLRRLLUUDDUDRRLLRLDUUUDDDUUDDLUDRLLLRRLLDRLDLLLUDLRLDRRRLLD

result:

ok Valid Solution (Length = 180).

Test #10:

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

input:

5 3
011
111
110
111
011
3 1 2 1

output:

UUDDDLLRRUDLLRULLLRUULLRRULLRUDLLLRUUDDLLRUUDDDLLRRUDLLRULLLRUULLRRULLRUDLLLLDURLLURRLLUURLLLURLLDURRLLDDDUURLLDDUURLLLDURLLURRLLUURLLLURLLDURRLLDDDUU

result:

ok Valid Solution (Length = 150).

Test #11:

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

input:

4 5
11111
11111
11111
11111
3 2 1 3

output:

LRRLRRRLRRLLRRLLLUULRLRRLRRLRRRLRRLLRRLLLLRLRRLRRLRRRLRRLLRRLLLUUDDUUUDDDLRLRRLRRLRRRLRRLLLRRLRRLRRRLRRLLRRLLLUULRLRRLRRLRRRLLRRRLRRLRRLRLUULLLRRLLRRLRRRLRRLRRLLLRRLRRRLRRLRRLRLDDDUUUDDUULLLRRLLRRLRRRLRRLRRLRLLLLRRLLRRLRRRLRRLRRLRLUULLLRRLLRRLRRRLRRL

result:

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