QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333096 | #7751. Palindrome Path | sumi007 | WA | 0ms | 3652kb | C++14 | 3.4kb | 2024-02-19 17:10:22 | 2024-02-19 17:10:22 |
Judging History
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)