QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333096#7751. Palindrome Pathsumi007WA 0ms3652kbC++143.4kb2024-02-19 17:10:222024-02-19 17:10:22

Judging History

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

  • [2024-02-19 17:10:22]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3652kb
  • [2024-02-19 17:10:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define i64 __int128
#define db double
#define ldb long double
#define ull unsigned long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(i) (i&-i) 
const int N = 55;
int n,m,idx,sx,sy,ex,ey,st,ed,las[N*N],a[N][N],id[N][N],fa[N*N],vis[N*N];
int dis[N*N][4],typ[N][N];
char opt[5] = {'W','U','R','L','D'};
vector<char> ans;
vector<int> path;
vector<int> e[N*N];
int find(int u){
    if(u==fa[u]) return u;
    return fa[u] = find(fa[u]);
}
void merge(int u,int v){
    e[u].pb(v),e[v].pb(u);
    u = find(u),v = find(v);
    if(u==v) return ;
    fa[u] = v;
}
void move(int u,int v){
    int w = typ[u][v];
    int ds = dis[u][5-w],dt = dis[ed][w];
    if(dt<ds){
        for(int i=1;i<=dt;i++) ans.pb(opt[5-w]);
        for(int i=1;i<=dt+1;i++) ans.pb(opt[w]);
    }else{
        for(int i=1;i<=ds+1;i++) ans.pb(opt[5-w]);
        for(int i=1;i<=ds+1;i++) ans.pb(opt[w]);
    }
}
void dfs(int u,int fa){
    vis[u] = 1;
    for(int v:e[u]){
        if(vis[v]) continue;
        move(u,v);
        dfs(v,u);
    }
    las[u] = fa;
    if(fa) move(u,fa);
}

int 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 ch;cin >> ch;
            a[i][j] = ch-'0';
            if(a[i][j]) id[i][j] = ++idx;
        }
    }
    cin >> sx >> sy >> ex >> ey;
    st = id[sx][sy],ed = id[ex][ey];
    if(!st || !ed) cout << -1,exit(0);
    for(int i=1;i<=idx;i++) fa[i] = i;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int u = id[i][j];
            if(a[i][j] && a[i+1][j]) merge(id[i][j],id[i+1][j]);
            if(a[i][j] && a[i][j+1]) merge(id[i][j],id[i][j+1]);
            typ[u][id[i+1][j]] = 4,typ[id[i+1][j]][u] = 1;
            typ[u][id[i][j+1]] = 2,typ[id[i][j+1]][u] = 3;
            // char opt[5] = {'W','U','R','L','D'};
        }
    }
    for(int i=1;i<=idx;i++) fa[i] = find(i);
    for(int i=1;i<idx;i++) if(fa[i]!=fa[i+1]) cout << -1,exit(0);
    for(int i=1;i<=n;i++){
        for(int j=n;j>=1;j--){
            int u = id[i][j],v = id[i][j+1];
            if(!u) continue;
            if(!v) dis[u][2] = 0;
            else dis[u][2] = dis[v][2]+1;
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=n;j++){
            int u = id[i][j],v = id[i+1][j];
            if(!u) continue;
            if(!v) dis[u][4] = 0;
            else dis[u][4] = dis[v][4]+1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int u = id[i][j],v = id[i-1][j];
            if(!u) continue;
            if(!v) dis[u][1] = 0;
            else dis[u][1] = dis[v][1]+1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int u = id[i][j],v = id[i][j-1];
            if(!u) continue;
            if(!v) dis[u][3] = 0;
            else dis[u][3] = dis[v][3]+1;
        }
    }
    dfs(st,0);
    stack<int> stk;int now = ed; 
    while(now!=st) stk.push(now),now = las[now];
    stk.push(st);
    while(stk.size()>1){
        int u = stk.top();stk.pop();
        move(u,stk.top());
    }
    for(char x:ans) cout << x;
    reverse(ans.begin(),ans.end());
    for(char x:ans) cout << x;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3652kb

input:

2 2
11
11
1 1 2 2

output:

UDLRDUUDRLDUUDLRRLDUUDLRDUUDRLDU

result:

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