QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394401#7751. Palindrome PathOccDreamerWA 0ms3780kbC++143.9kb2024-04-20 14:19:512024-04-20 14:19:51

Judging History

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

  • [2024-04-20 14:19:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3780kb
  • [2024-04-20 14:19:51]
  • 提交

answer

//OccDreamer
#include<bits/stdc++.h>

#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define OccDreamer
//#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(int x){write(x), putchar(32);}
	inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;

const int MAXN = 35;
const int mod = 998244353;
const int rx[]={1,-1,0,0}, ry[]={0,0,1,-1};
const char dir[]={'D','U','R','L'};

int ax, ay, bx, by;
int n, m, tot, all[4];

char s[MAXN][MAXN];

bool vis[MAXN][MAXN];

vc<char> ans;

inline void dfs(int x, int y){
	vis[x][y]=1; --tot;
	for(int i=0;i<4;++i){
		int tx=x+rx[i], ty=y+ry[i];
		if(tx>=1 && ty>=1 && tx<=n && ty<=m && s[tx][ty]=='1' && !vis[tx][ty]) dfs(tx,ty);	
	}
	return ;
}

inline void construct(int x, int y){
	vis[x][y]=1;
	for(int i=0;i<4;++i){
		int tx=x+rx[i], ty=y+ry[i];
		if(tx>=1 && ty>=1 && tx<=n && ty<=m && s[tx][ty]=='1' && !vis[tx][ty]){
			int sum=0, A=x, B=y;
			while(s[A][B]=='1' && A>=1 && B>=1 && A<=n && B<=m) A+=rx[i^1], B+=ry[i^1], sum++;
			if(sum<all[i]){
				for(int j=1;j<=sum;++j) ans.pb(dir[i^1]); 
				for(int j=1;j<=sum;++j) ans.pb(dir[i]);
			}
			else{
				for(int j=1;j<all[i];++j) ans.pb(dir[i^1]);
				for(int j=1;j<=all[i];++j) ans.pb(dir[i]);	
			}
			construct(tx,ty); 
			A=tx, B=ty;
			while(s[A][B]=='1' && A>=1 && B>=1 && A<=n && B<=m) A+=rx[i], B+=ry[i], sum++;
			if(sum<all[i^1]){
				for(int j=1;j<=sum;++j) ans.pb(dir[i]); 
				for(int j=1;j<=sum;++j) ans.pb(dir[i^1]);
			}
			else{
				for(int j=1;j<all[i^1];++j) ans.pb(dir[i]);
				for(int j=1;j<=all[i^1];++j) ans.pb(dir[i^1]);	
			}
		}
	}
	return ;
}

inline void construct2(int x, int y){
	if(x==bx && y==by){
		for(auto i:ans) putchar(i);
		reverse(ans.begin(),ans.end());
		for(auto i:ans) putchar(i);
		exit(0);	
	}
	vis[x][y]=1;
	for(int i=0;i<4;++i){
		int tx=x+rx[i], ty=y+ry[i];
		if(tx>=1 && ty>=1 && tx<=n && ty<=m && s[tx][ty]=='1' && !vis[tx][ty]){
			int sum=0, A=x, B=y;
			while(s[A][B]=='1' && A>=1 && B>=1 && A<=n && B<=m) A+=rx[i^1], B+=ry[i^1], sum++;
			if(sum<all[i]){
				for(int j=1;j<=sum;++j) ans.pb(dir[i^1]); 
				for(int j=1;j<=sum;++j) ans.pb(dir[i]);
			}
			else{
				for(int j=1;j<all[i];++j) ans.pb(dir[i^1]);
				for(int j=1;j<=all[i];++j) ans.pb(dir[i]);	
			}
			construct2(tx,ty); 
			A=tx, B=ty;
			while(s[A][B]=='1' && A>=1 && B>=1 && A<=n && B<=m) A+=rx[i], B+=ry[i], sum++;
			if(sum<all[i^1]){
				for(int j=1;j<=sum;++j) ans.pb(dir[i]); 
				for(int j=1;j<=sum;++j) ans.pb(dir[i^1]);
			}
			else{
				for(int j=1;j<all[i^1];++j) ans.pb(dir[i]);
				for(int j=1;j<=all[i^1];++j) ans.pb(dir[i^1]);	
			}
		}
	}
	return ;
}

signed main(){
	n=read(), m=read();
	for(int i=1;i<=n;++i){
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;++j) tot+=s[i][j]=='1';	
	}
	ax=read(), ay=read(), bx=read(), by=read();
	if(s[ax][ay]=='0' || s[bx][by]=='0') return eprint(-1), 0;
	dfs(ax,ay); if(tot) return eprint(-1), 0; memset(vis,0,sizeof vis);
	for(int i=0;i<4;++i){
		all[i]=0; int A=bx, B=by;
		while(s[A][B]=='1' && A>=1 && B>=1 && A<=n && B<=m) A=A+rx[i], B=B+ry[i], all[i]++;	
	}
	construct(ax,ay); memset(vis,0,sizeof vis); construct2(ax,ay);
	return 0;
}


Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3652kb

input:

2 2
11
11
1 1 2 2

output:

DRDUDRLLDUUDRRDUUDLLRDUDRD

result:

ok Valid Solution (Length = 26).

Test #2:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

1 1
1
1 1 1 1

output:


result:

ok Valid Solution (Length = 0).

Test #4:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

UDDLLRRDUDDUUDDDUUUDDDUUUULLRRRUDUDDUDDUDDDDDUUUUDDDUUUUDDDUUUUDDDUUUURLLRLLUDUDDRLLUDDUDDDDDUUUUDDDUUUUDDDUUUDDDUUUUUDDUDDLLRRRDDDUUUUDDDUUUULLRRRUDDUDDUDDUDDRLLDDDUUUUUUUUDDDLLRDDUDDUDDUDDURRRLLUUUUDDDUUUUDDDRRRLLDDUDDUUUUUDDDUUUDDDUUUUDDDUUUUDDDDDUDDULLRDDUDULLRLLRUUUUDDDUUUUDDDUUUUDDDUUUUDDDDDUD...

result:

ok Valid Solution (Length = 338).

Test #5:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

RDDDDRLRRLLDUDDUUDDDUUUDDDDUUUURRRLLLRRRRLLLLDDDDRRRRRLLLLLDDDDUUUUUDDDDUUUUURRRRRLLLLLDDDDUUUUUDDDDUUUUURRDDRRRRRLLLLLDDRRDDDDUUUUUDDDDUUUUUDDDDUUUUUDDDDUUUUURRRRLLLLLRDDDDDDDDRLLLLLRRRRUUUUUDDDDUUUUUDDDDUUUUUDDDDUUUUUDDDDRRDDLLLLLRRRRRDDRRUUUUUDDDDUUUUUDDDDLLLLLRRRRRUUUUUDDDDUUUUUDDDDLLLLLRRRRRDDD...

result:

ok Valid Solution (Length = 346).

Test #6:

score: 0
Accepted
time: 0ms
memory: 3780kb

input:

5 3
111
100
111
001
111
4 3 3 2

output:

DRLRLLLRRLRRUURLRLLUULRLRRRLLRLLDDLRRLRRDDRLRLLLRRLRRUURLLRUURRLRRLLLRLRDDRRLRRLDDLLRLLRRRLRLUULLRLRUURRLRRLLLRLRD

result:

ok Valid Solution (Length = 114).

Test #7:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

UDRUDUUDDURUUUUUDDDUUDDDUUDDDLULLUUUUDDDUUDDDRUUDRUDUUDDURUUUUUDDDUUDDDUUDDDLULLUUUULLULDDDUUDDDUUDDDUUUUURUDDUUDURDUURDDDUUDDDUUUULLULDDDUUDDDUUDDDUUUUURUDDUUDURDU

result:

ok Valid Solution (Length = 164).

Test #8:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

5 3
101
111
100
111
100
4 1 2 2

output:

DUUUUDLRLRRUDRLLRLLDDLRLRRRLLRLLDUUUUDLRRLDUUUUDLLRLLRRRLRLDDLLRLLRDURRLRLDUUUUD

result:

ok Valid Solution (Length = 80).

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3704kb

input:

5 5
01110
10110
11110
11011
11100
2 4 5 1

output:

DDLRLDDDUUUULDUDDUULLRRLLLLRRRDDLDDLLRRLLDUDDUUDDDUUUDDDLLRRRDDDUUUDDDUUULLRRRLLRRRDDDUUUUDDLRLDDDUUUULDUDDUULLRRLLLLRRRDDLDDLLRRLLLLRRLLDDLDDRRRLLLLRRLLUUDDUDLUUUUDDDLRLDDUUUUDDDRRRLLRRRLLUUUDDDUUUDDDRRRLLDDDUUUDDDUUDDUDLLRRLLDDLDDRRRLLLLRRLLUUDDUDLUUUUDDDLRLDD

result:

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