QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394574 | #7751. Palindrome Path | Andy_Lin | WA | 0ms | 3936kb | C++14 | 2.5kb | 2024-04-20 16:20:19 | 2024-04-20 16:20:20 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 32
#define pii pair<int,int>
#define ppp tuple<int,int,int,int>
int sr,sc,er,ec,n,m,a[N][N];
const short dd[4][2]={{1,0},{0,1},{0,-1},{-1,0}};
char dy[5]="DRLU";
vector<int>ed;
namespace bl{
bool flag[N][N];
void dfs(int x,int y){
flag[x][y]=1;
for(int i=0;i<4;++i){
int tx=x+dd[i][0],ty=y+dd[i][1];
if(!a[tx][ty]||flag[tx][ty])continue;
ed.push_back(i);
dfs(tx,ty);
ed.push_back(3-i);
}
}
}
namespace xy{
bool flag[N][N][N][N];
pair<ppp,int> pre[N][N][N][N];
queue<ppp>q;
pii solve(){
flag[sr][sc][er][ec]=1;
if(sr==er&&sc==ec){
return {sr,sc};
}
q.push({sr,sc,er,ec});
while(!q.empty()){
int x,y,xx,yy;tie(x,y,xx,yy)=q.front();q.pop();
for(int i=0;i<4;++i){
int txx=xx+dd[3-i][0],tyy=yy+dd[3-i][1],tx=x,ty=y;
if(a[x+dd[i][0]][y+dd[i][1]])tx+=dd[i][0],ty+=dd[i][1];
if(!a[xx+dd[i][0]][yy+dd[i][1]]&&!flag[tx][ty][xx][yy]){
flag[tx][ty][xx][yy]=1;
pre[tx][ty][xx][yy]={{x,y,xx,yy},i};
if(tx==xx&&ty==yy)return {tx,ty};
q.push({tx,ty,xx,yy});
}
if(!a[xx+dd[3-i][0]][yy+dd[3-i][1]])continue;
if(flag[tx][ty][txx][tyy])continue;
flag[tx][ty][txx][tyy]=1;
pre[tx][ty][txx][tyy]={{x,y,xx,yy},i};
if(tx==txx&&ty==tyy)return {tx,ty};
q.push({tx,ty,txx,tyy});
}
}
return {0,0};
}
}
vector<int>md;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%1d",&a[i][j]);
}
}
scanf("%d%d%d%d",&sr,&sc,&er,&ec);
bl::dfs(er,ec);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(a[i][j]!=bl::flag[i][j]){
puts("-1");return 0;
}
}
}
for(int i=ed.size()-1;i>=0;--i){
putchar(dy[ed[i]]);
int u=dd[ed[i]][0],v=dd[ed[i]][1];
if(a[sr+u][sc+v])sr+=u,sc+=v;
}
int x,y,xx,yy;
if(n!=2)return 0;
tie(x,y)=xy::solve();xx=x,yy=y;
while(make_tuple(x,y,xx,yy)!=make_tuple(sr,sc,er,ec)){
int tx,ty,txx,tyy;
tie(tx,ty,txx,tyy)=xy::pre[x][y][xx][yy].first;
md.push_back(xy::pre[x][y][xx][yy].second);
x=tx;y=ty;xx=txx;yy=tyy;
}
for(int i=md.size()-1;i>=0;--i){
putchar(dy[md[i]]);
}
for(int i=0;i<md.size();++i){
putchar(dy[md[i]]);
}
for(int i=0;i<ed.size();++i){
putchar(dy[ed[i]]);
}
puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3720kb
input:
2 2 11 11 1 1 2 2
output:
RDLRULDRRDLURLDR
result:
ok Valid Solution (Length = 16).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3712kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
ULLDRDLDRRURDDLLLRRRUUUUDDLDLLURULURRD
result:
wrong answer Solution Not Palindrome