QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333360#7751. Palindrome Pathyz_lyWA 0ms3824kbC++142.4kb2024-02-19 20:53:242024-02-19 20:53:24

Judging History

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

  • [2024-02-19 20:53:24]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3824kb
  • [2024-02-19 20:53:24]
  • 提交

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