QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#333360 | #7751. Palindrome Path | yz_ly | WA | 0ms | 3824kb | C++14 | 2.4kb | 2024-02-19 20:53:24 | 2024-02-19 20:53:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
int f=1,x=0;
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
inline void work(int k){
if(k<0){
putchar('-');
k=-k;
}
if(k>9)
work(k/10);
putchar(k%10+'0');
}
/*
空地不连通无解,否则猜想一定有解
因为要求是回文串,所以我们考虑构造一个A然后再翻转复制
那么就要求我们这个点再移动的同时,终点做翻转的操作后必须回到原点
我们进行分类讨论,这里以我们需要向右走为例,其它情况同理
看看起点左边的障碍和终点右边的障碍谁离起点和终点近一些,设离得近的那一个距离为k
如果是起点近一些,我们就向左走k+1步再向右走k+1步
终点近一些就向左走k步,再向右走k+1步
容易发现这样是对的,发现上界是12mnmax(n,m),完全可过
*/
int n,m,ex,ey,bx,by,vis[35][35],num,num1,sum;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
vector<int> q,p;
char a[35][35],ans[1000005],g[4]={'L','R','U','D'};
void solve(int x,int y,int f){
int now=bx,now1=by,gg=0;
while(a[x][y]=='1'&&a[now][now1]=='1'){
x+=dx[f];
y+=dy[f];
now+=dx[f^1];
now1+=dy[f^1];
gg++;
}
if(a[x][y]=='0'){
for(int i=sum+1;i<=sum+gg;i++){
ans[i]=g[f];
}
for(int i=sum+gg+1;i<=sum+2*gg;i++){
ans[i]=g[f^1];
}
sum+=2*gg;
}
else{
for(int i=sum+1;i<=sum+gg-1;i++){
ans[i]=g[f];
}
for(int i=sum+gg;i<=sum+2*gg-1;i++){
ans[i]=g[f^1];
}
sum+=2*gg-1;
}
}
void dfs(int x,int y){
if(x==bx&&y==by)
p=q;
num++;
vis[x][y]=1;
for(int i=0;i<4;i++){
int hx=x+dx[i],hy=y+dy[i];
if(vis[hx][hy]||a[hx][hy]=='0')
continue;
solve(x,y,i);
q.emplace_back(i);
dfs(hx,hy);
q.pop_back();
solve(hx,hy,i^1);
}
}
int main(){
n=read();
m=read();
for(int i=1;i<=n;i++){
scanf("%s",a[i]+1);
for(int j=1;j<=m;j++){
num1+=(a[i][j]=='0');
}
}
for(int i=1;i<=n;i++){
a[i][0]=a[i][m+1]='0';
}
for(int i=1;i<=m;i++){
a[0][i]=a[n+1][i]='0';
}
ex=read();
ey=read();
bx=read();
by=read();
dfs(ex,ey);
if(num+num1<n*m){
printf("-1");
return 0;
}
int now=ex,now1=ey;
for(auto i:p){
solve(now,now1,i);
now+=dx[i],now1+=dy[i];
}
for(int i=1;i<=sum;i++){
putchar(ans[i]);
}
for(int i=sum;i;i--){
putchar(ans[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3764kb
input:
2 2 11 11 1 1 2 2
output:
RRLLDDUURRRLLDRRRLLDDUUUUDDLLRRRDLLRRRUUDDLLRR
result:
ok Valid Solution (Length = 46).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
LLRRUDDRLLRLLRRLLUDDLLRRRLLLRRRLLRRUUDDRLLRLLRRLLLLRRRLLLRRRLLRRDDDUUUURLLRLLRRLLDDDDUUUUDDDUUULLRRRDDUULLLRRRLLRRRLLRLLRRLLLLRRRUDDRRLLUDDLLRRRLLLRRRLLRRDDDUUURLLLLRUUUDDDRRLLRRRLLLRRRLLDDULLRRDDURRRLLLLRRLLRLLRRRLLRRRLLLUUDDRRRLLUUUDDDUUUUDDDDLLRRLLRLLRUUUUDDDRRLLRRRLLLRRRLLLLRRLLRLLRDDUURRLLRRRLL...
result:
ok Valid Solution (Length = 326).
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3824kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
RRRDDDDDUUUUUDDDDUUUURRRRRLLLLLRRRRLLLLRRRLLLRRLLDDDDDDDUUUUUDDDDUUUUDDDUUUDDUURRRRDDDUURRRRRLLLLLRRRRLLLLDDDUURRRLLLRRLLDDRRDDDDDUUUURRDDRRRRRLLLLLRRRRLLLLRRRLLLRRRDDDDDUUUUUDDDDUUUURRRRRLLLLLRRRRLLLLRRRLLLRRLLDDDUUUDDUUUUDDUUUDDDLLRRLLLRRRLLLLRRRRLLLLLRRRRRUUUUDDDDUUUUUDDDDDRRRLLLRRRLLLLRRRRLLLLLR...
result:
wrong answer (2,3) Not Visited