QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#332819#7751. Palindrome Pathc20230201WA 1ms3860kbC++143.1kb2024-02-19 16:07:212024-02-19 16:07:22

Judging History

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

  • [2024-02-19 16:07:22]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3860kb
  • [2024-02-19 16:07:21]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

int sx,sy,ex,ey;

int a[33][33];
int vis[33][33], fa[33][33];
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};

vector<char> ans;
vector<int> g[33][33];

void dfs(int x,int y) {
    vis[x][y]=1;
    for(int d=0;d<4;d++) {
        int tx=x+dx[d], ty=y+dy[d];
        if(!a[tx][ty]||vis[tx][ty]) continue;
        g[x][y].push_back(d);
        fa[tx][ty]=d^1;
        dfs(tx,ty);
    }
    return ;
}

void calc(int x,int y,int d) {
    if(d==0) {
        int k=0;
        while(a[x-k][y]&&a[ex+k][ey]) k++;
        if(!a[ex+k][ey]) {
            for(int j=1;j<k;j++) ans.push_back('U');
            for(int j=1;j<=k;j++) ans.push_back('D');
        }else {
            for(int j=1;j<=k;j++) ans.push_back('U');
            for(int j=1;j<=k;j++) ans.push_back('D');
        }
    }
    if(d==1) {
        int k=0;
        while(a[x+k][y]&&a[ex-k][ey]) k++;
        if(!a[ex-k][ey]) {
            for(int j=1;j<k;j++) ans.push_back('D');
            for(int j=1;j<=k;j++) ans.push_back('U');
        }else {
            for(int j=1;j<=k;j++) ans.push_back('D');
            for(int j=1;j<=k;j++) ans.push_back('U');
        }
    }
    if(d==2) {
        int k=0;
        while(a[x][y-k]&&a[ex][ey+k]) k++;
        if(!a[ex][ey+k]) {
            for(int j=1;j<k;j++) ans.push_back('L');
            for(int j=1;j<=k;j++) ans.push_back('R');
        }else {
            for(int j=1;j<=k;j++) ans.push_back('L');
            for(int j=1;j<=k;j++) ans.push_back('R');
        }
    }
    if(d==3) {
        int k=0;
        while(a[x][y+k]&&a[ex][ey-k]) k++;
        if(!a[ex][ey-k]) {
            for(int j=1;j<k;j++) ans.push_back('R');
            for(int j=1;j<=k;j++) ans.push_back('L');
        }else {
            for(int j=1;j<=k;j++) ans.push_back('R');
            for(int j=1;j<=k;j++) ans.push_back('L');
        }
    }
    return ;
}

void dfs2(int x,int y) {
    for(auto d:g[x][y]) {
        calc(x,y,d);
        dfs2(x+dx[d],y+dy[d]);
        calc(x,y,d^1);
    }
    return ;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int n,m; cin>>n>>m;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            char ch; cin>>ch;
            a[i][j]=ch-'0';
        }
    }
    cin>>sx>>sy>>ex>>ey;
    dfs(sx,sy);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(a[i][j]&&vis[i][j]==0) {
                cout<<"-1\n";
                exit(0);
            }
        }
    }
    dfs2(sx,sy);
    vector<int> op;
    int fx=ex, fy=ey, tx=sx, ty=sy;
    while(fx!=sx||fy!=sy) {
        int d=fa[fx][fy];
        fx+= dx[d], fy+= dy[d];
        op.push_back(d^1);
    }
    while(op.size()) {
        calc(sx,sy,op.back());
        int d=op.back(); op.pop_back();
        sx+= dx[d], sy+= dy[d];
        if(d==0) ans.push_back('D');
        if(d==1) ans.push_back('U');
        if(d==2) ans.push_back('R');
        if(d==3) ans.push_back('L');
    }
    for(int i=ans.size()-1;i>=0;i--) ans.push_back(ans[i]);
    for(auto x:ans) cout<<x;
    cout<<'\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
11
11
1 1 2 2

output:

DRDUDRLLDUUDDRRRRDDUUDLLRDUDRD

result:

ok Valid Solution (Length = 30).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

UDDLLRRDUDDUUDDDUUUDDDUUUULLRRRUDUDDUDDUDDDDUUDDDUUUDDDUUUUDDDUUUURLLRLLUDUDDRLLUDDUDDDDUUDDDUUUDDDUUUDDDUUUUUDDUDDLLRRDDDUUUUDDDUUUULLRRRUDDUDDUDDUDDRLLDDUUUUDDLLRDDUDDUDDUDDURRRLLUUUUDDDUUUUDDDRRLLDDUDDUUUUUDDDUUUDDDUUUDDDUUDDDDUDDULLRDDUDULLRLLRUUUUDDDUUUUDDDUUUDDDUUDDDDUDDUDDUDURRRLLUUUUDDDUUUDD...

result:

ok Valid Solution (Length = 314).

Test #5:

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

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

RDDDDRLRRLLDUDDUUDDDUUUDDDDUUUURRRLLLRRRRLLLLDDDDRRRRRLLLLLDDUUDDDUUURRRRRLLLLLDDDDUUUUDDDDUUUUURRDDRRRRLLLDDRRDDUUDDDUUUDDDDUUUUDDDDUUUUURRLLRRDDDDDDDDDDDDDDDDRRLLRRUUUUUDDDDUUUUDDDDUUUDDDUUDDRRDDLLLRRRRDDRRUUUUUDDDDUUUUDDDDLLLLLRRRRRUUUDDDUUDDLLLLLRRRRRDDDDLLLLRRRRLLLRRRUUUUDDDDUUUDDDUUDDUDLLRRLRD...

result:

ok Valid Solution (Length = 304).

Test #6:

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

input:

5 3
111
100
111
001
111
4 3 3 2

output:

DRLRLLLRRLRRUURLRLLUULRLRRRLLRLLDDLRRLRRDUURLLLLRUUDRRLRRLDDLLRLLRRRLRLUULLRLRUURRLRRLLLRLRD

result:

ok Valid Solution (Length = 92).

Test #7:

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

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

UDRUDUUDDURUUUUUDDUUDDDUUDDDLULLUUUUDDUUDDDRUUDDLLUUUUUUUULLDDUURDDDUUDDUUUULLULDDDUUDDDUUDDUUUUURUDDUUDURDU

result:

ok Valid Solution (Length = 108).

Test #8:

score: -100
Wrong Answer
time: 1ms
memory: 3584kb

input:

5 3
101
111
100
111
100
4 1 2 2

output:

DUUUUDLRLRRUDRLLRLLDDLRLRRRLLRLLUUUULRRRRLUUUULLRLLRRRLRLDDLLRLLRDURRLRLDUUUUD

result:

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