QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#688805#7751. Palindrome Pathicpc_zhzx034TL 995ms3996kbC++142.8kb2024-10-30 13:40:152024-10-30 13:40:15

Judging History

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

  • [2024-10-30 13:40:15]
  • 评测
  • 测评结果:TL
  • 用时:995ms
  • 内存:3996kb
  • [2024-10-30 13:40:15]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define fi first
#define se second
#define mk make_pair
#define eb emplace_back
#define rep(i,l,r) for(int i=(l); i<=(r); ++i)
#define rep_(i,l,r) for(int i=(l); i>=(r); --i)
typedef long long lr;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
constexpr int mod1=998244353,mod2=1e9+7;
constexpr db pi=3.141592653589793,eps=1e-9;
constexpr int inf32=0x3f3f3f3f,Inf32=0xc0c0c0c0;
constexpr lr inf64=0x3f3f3f3f3f3f3f3f,Inf64=0xc0c0c0c0c0c0c0c0;
template<typename T>il T Max(T x,T y) { return (x>y)? x:y; }
template<typename T>il T Min(T x,T y) { return (x<y)? x:y; }
template<typename T>il T gcd(T x,T y) { return (!y)? x:gcd(y,x%y); }
template<typename T>il T Abs(T x) { return (x>0)? x:(-x); }
template<typename T>il T Rnd(T l,T r,mt19937_64 &eng)
{
	uniform_int_distribution<T> uid(l,r);
	return uid(eng);
}
mt19937_64 eng(chrono::high_resolution_clock::now().time_since_epoch().count());
constexpr int N=32;
int n,m,sx,sy,fx,fy;
int cnt,vis[N][N];
string s[N],t;
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
il int val(int X,int Y)
{
	if(X<1||X>n||Y<1||Y>m||!s[X][Y])
		return 0;
	return 1;
}
il void chk()
{
	cnt=(sx==fx&&sy==fy)? 1:2;
	rep(i,1,n)
		rep(j,1,m)
		{
			vis[i][j]=0;
			if(!s[i][j])
				++cnt;
		}
	vis[sx][sy]=1,vis[fx][fy]=1,t="";
	int nsx=sx,nsy=sy,nfx=fx,nfy=fy;
	rep(p,1,90000)
	{
		if(cnt==n*m&&Abs(nsx-nfx)+Abs(nsy-nfy)<=1)
		{
			rep(i,0,p-2)
				cout<<t[i];
			if(nsx>nfx)
				cout<<'U';
			if(nsx<nfx)
				cout<<'D';
			if(nsy>nfy)
				cout<<'L';
			if(nsy<nfy)
				cout<<'R';
			rep_(i,p-2,0)
				cout<<t[i];
			cout<<'\n';
			exit(0);
		}
		int flag=0;
		rep(i,0,3)
			flag|=(val(nfx-dx[i],nfy-dy[i])|(!val(nfx+dx[i],nfy+dy[i])));
		if(!flag)
			return;
		int dir=eng()&3;
		while(!(val(nfx-dx[dir],nfy-dy[dir])|(!val(nfx+dx[dir],nfy+dy[dir]))))
			dir=eng()&3;
		if(dir==0)
			t+="L";
		if(dir==1)
			t+="R";
		if(dir==2)
			t+="U";
		if(dir==3)
			t+="D";
		if(val(nsx+dx[dir],nsy+dy[dir]))
			nsx+=dx[dir],nsy+=dy[dir];
		int op=Rnd(val(nfx+dx[dir],nfy+dy[dir]),val(nfx-dx[dir],nfy-dy[dir]),eng);
		if(op)
			nfx-=dx[dir],nfy-=dy[dir];
		if(!vis[nsx][nsy])
			vis[nsx][nsy]=1,++cnt;
		if(!vis[nfx][nfy])
			vis[nfx][nfy]=1,++cnt;
	}
}
il void Solve()
{
	cin>>n>>m;
	rep(i,1,n)
		cin>>s[i],s[i]=" "+s[i];
	cin>>sx>>sy>>fx>>fy;
	rep(i,1,n)
		rep(j,1,m)
			s[i][j]^=48;
	int Q=200;
	rep(i,1,Q)
		chk();
	cout<<-1<<'\n';
	return;
}
int main()
{
#ifdef LOCAL
	string fpre="test",isuf="in",osuf="out";
	assert(freopen((fpre+"."+isuf).c_str(),"r",stdin));
	assert(freopen((fpre+"."+osuf).c_str(),"w",stdout));
#endif
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T=1;
	while(T--)
		Solve();
	return 0;
}

详细

Test #1:

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

input:

2 2
11
11
1 1 2 2

output:

DRLUDRLUDURUDULRDULRD

result:

ok Valid Solution (Length = 21).

Test #2:

score: 0
Accepted
time: 756ms
memory: 3996kb

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

RDLDLUUDDUUDLUULDURLDRLRRRLDRRLUDLDRDUDLDLULDUDRUULLDDDUUDULULRDLRRDDUUDLLRDLLLUDDDURDDDLUDLULRDLULRDDRULULUDRLURRRRRRLDDLDDUULDRULLDRLRLRLDLDRDUDLDRDDUUDUDUDLDRDLULULDRUUDURRUDUURDLULULDRDLDUDUDUUDDRDLDUDRDLDLRLRLRDLLURDLUUDDLDDLRRRRRRULRDULULURDDRLULDRLULDULDDDRUDDDULLLDRLLDUUDDRRLDRLULUDUUDDDLLUU...

result:

ok Valid Solution (Length = 348).

Test #5:

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

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

DRLLRDDUUURRDDLRLDDULDUDDDLDUUDDLUDRRULDDUDDDDRLULDUDRRDRDRURDURUDRDRURRLDUUDRRLRDULRUUULLDDULURDULRLLLDRLUDLLLLURRLLRURRDUULRUDDUDRUULRRUDDULLUUDUDRLLURLLURDLDLDRULLRULLRDUDUULLUDDURRLUURDUDDURLUUDRRURLLRRULLLLDULRDLLLRLUDRULUDDLLUUURLUDRLRRDUUDLRRURDRDURUDRURDRDRRDUDLULRDDDDUDDLURRDULDDUUDLDDDUDLU...

result:

ok Valid Solution (Length = 319).

Test #6:

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

input:

5 3
111
100
111
001
111
4 3 3 2

output:

RDLLUURDDURULLDRULULDRDRULRUDRDURDRDLDRRRDUDLRDULRLDRRUDLUDDDLLRURLDLDDLRUDULDRLUDDDUDDRRUUULLUUULLUUURRDDUDDDULRDLUDURLDDLDLRURLLDDDULDURRDLRLUDRLDUDRRRDLDRDRUDRDURLURDRDLULURDLLURUDDRUULLDR

result:

ok Valid Solution (Length = 191).

Test #7:

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

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

UDRUDRURLURLLRLULDLULLURLDUDUDDLLDRRLRLRLLRULLLRLRRUUDLLULURDURDRRRDDUUULDLDDLUDDRURULULRLLLRDLLDLLLRDDUDDLUDLLUDLUULDULRRRRRRLUDRLULRLUUULRDULRLDDDURUDUULRRUDDDLLRDLLDUDULRLUUURDLDDDUDUUDLLLDUDRURRLUDDURLUDLDLRDRLRLDURURLRDLULUDLRRLDUDDRUUDDLRUDRLRURURUUDDDDLLUDRLURLRRUUULUDLRRRRLRRRLUDULRLUULDUDDL...

result:

ok Valid Solution (Length = 753).

Test #8:

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

input:

5 3
101
111
100
111
100
4 1 2 2

output:

LRDDDULLRRRRRURUURRDLRUDURRRLRUURLLUULDDRRLULULRDDLRDLRLLLLRRRUDULURLRLLLLLULUDRRDULULLLLLRLRULUDURRRLLLLRLDRLDDRLULULRRDDLUULLRUURLRRRUDURLDRRUURURRRRRLLUDDDRL

result:

ok Valid Solution (Length = 160).

Test #9:

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

input:

5 5
01110
10110
11110
11011
11100
2 4 5 1

output:

LRDLLDLDLDUUUURURDRLUDUURRDRURRRUUURDDRURDRDUDLULUDDDRRDDULUUDURUDUDURRDUDURRDULLDDRLLLDDRRDRRLRLUDRLUULRRRRRUUULLRDDULRDUDLDRDDUDDULLLLULDLRLUDLRLLLRRLRUDUUDLRRLURLRUDLRULURRUDLLRRLRULURULRRLRLULRDULDLLRLLRUDLRRLRRUUULDDUURLRDRDLRUULDRLLUDDRRRLULLULLUURRLRRRLLLUULLRRLUULDDDLULDLLULDLLRRRRUUURRRLRLR...

result:

ok Valid Solution (Length = 841).

Test #10:

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

input:

5 3
011
111
110
111
011
3 1 2 1

output:

UUDDUULULUDRUULDLULLLRRUDRRRULDDDDLURRRDURRLLLULDLUURDULULUUDDUU

result:

ok Valid Solution (Length = 64).

Test #11:

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

input:

4 5
11111
11111
11111
11111
3 2 1 3

output:

URLLLUURLURUDRLLURLDRLRLDURRLDLDUUUDRRDDRLRLLUDRRDLRRUUUURRLDRRDULLRLRDDRRDUUUDLDLRRUDLRLRDLRULLRDURULRUULLLRU

result:

ok Valid Solution (Length = 110).

Test #12:

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

input:

5 5
11111
10101
11111
10101
11111
2 5 1 1

output:

LLULRULDURRRUUURRLRLRULDLUDLRLRLUDDDULRDLDDRDLLLRUDDDDLRDUDRDRRLRDLUULUDLDRLLUDLDDUDUUDRRDRLUDUURLRRLLDRRULRDDDLRRLLLRURDRLDRRDLRDRURLLLRRLDDDRLURRDLLRRLRUUDULRDRRDUUDUDDLDULLRDLDULUULDRLRRDRDUDRLDDDDURLLLDRDDLDRLUDDDULRLRLDULDLURLRLRRUUURRRUDLURLULL

result:

ok Valid Solution (Length = 250).

Test #13:

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

input:

4 5
11111
10000
11111
00001
1 3 4 5

output:

RRDRURLRRUDRDRUDDLRULULLLULURLDDURDRDURRLRURDRR

result:

ok Valid Solution (Length = 47).

Test #14:

score: 0
Accepted
time: 739ms
memory: 3752kb

input:

3 5
10100
00010
00111
1 3 1 1

output:

-1

result:

ok No Solution.

Test #15:

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

input:

4 5
10001
11111
11100
11111
4 5 3 1

output:

LUDDDLDDDRURULRLDLULUUDDDLUDLLURULUULUUDLRDLRLDUDLLLRULRLRULUULRDDDULUURUDRUDDRRLLRUUURLLRRDDURDURUULUDDDRLUULURLRLURLLLDUDLRLDRLDUULUULURULLDULDDDUULULDLRLURURDDDLDDDUL

result:

ok Valid Solution (Length = 169).

Test #16:

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

input:

3 5
11111
10100
11111
1 2 3 5

output:

DRLDRRRURDURURLULRRUDUURUUDUURRDRLUDDLURURLDUUURLDRUDDDUDDUDDDUURRUURRRLRDLLLDLRLLLULRLLDLUUUDDDRUDDURDULURRULUDRUDDURDDDUUULDLLRLULLLRLDLLLDRLRRRUURRUUDDDUDDUDDDURDLRUUUDLRURULDDULRDRRUUDUURUUDURRLULRURUDRURRRDLRD

result:

ok Valid Solution (Length = 214).

Test #17:

score: 0
Accepted
time: 930ms
memory: 3664kb

input:

4 5
01110
10101
11011
10111
1 3 2 3

output:

-1

result:

ok No Solution.

Test #18:

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

input:

5 5
11111
11111
11111
11111
11111
1 3 5 2

output:

LLRLRDRRDLLRDULUUDULDDLLDRLLLDDLLULDDDLLLLURULRRDLDDLRLRRLRRURRRDLULUULULDDDLULUULULDRRRURRLRRLRLDDLDRRLURULLLLDDDLULLDDLLLRDLLDDLUDUULUDRLLDRRDRLRLL

result:

ok Valid Solution (Length = 149).

Test #19:

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

input:

5 5
11111
10101
11111
10101
11111
5 1 2 3

output:

LRLLUDRRULRRRUDUUDDDRLULDDDLLLUURDRDRDDDULDRRUDRLDRRRLLLLRDULDLDDULDLLRDDURLDDDLRLLUDUDULDURLRUULRDLRRDLLRULLRRUUDRUDURRLURURLDDRDLUDLDDURRRULDDULLUULLUDDLURRRUDDLDULDRDDLRURULRRUDURDUURRLLURLLDRRLDRLUURLRUDLUDUDULLRLDDDLRUDDRLLDLUDDLDLUDRLLLLRRRDLRDURRDLUDDDRDRDRUULLLDDDLULRDDDUUDURRRLURRDULLRL

result:

ok Valid Solution (Length = 296).

Test #20:

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

input:

5 5
11111
10000
11111
00001
11111
4 5 5 3

output:

DRDRLLULUULUULRRULRLRDUUULLLDRRDLRDLUDDDUUUDRLDDLUURLUULRRUDDUDUULLLURUUULRUUDLDLRURLLRDRDLDULDLRDDRUUURRRUDURUDRLUDUDLDDDDUULLDRUUDRUDLUULUDLLDDUULRRDURDDDUURDRURRDUURDDURDURULDUULUDUDRULUDLLRLDLUURUDLUUDDRRDLLDDLDDLLLRRRDRULRLDLRDULDRRLRUDDLRRRRRDLDULDDDDDDURRULDDLDLDRDULRDRDDLRUDLDDUDLLURLURRLURD...

result:

ok Valid Solution (Length = 1309).

Test #21:

score: 0
Accepted
time: 925ms
memory: 3756kb

input:

5 5
01010
10101
10101
11001
10011
4 1 5 4

output:

-1

result:

ok No Solution.

Test #22:

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

input:

5 5
10101
11111
10101
11111
11111
3 1 2 4

output:

LDLRLRUDLRURDLDLLRURULURLLLULLLLUUUUUDRRLURLURLLDDRRLDLDRLRRUURLDRRLLUUURRRRDLLRDURDLRURRLRDDDDDRLRRURLDRUDRLLDRRRRUUULLRRDLRUURRLRDLDLRRDDLLRULRULRRDUUUUULLLLULLLRULURURLLDLDRURLDURLRLDL

result:

ok Valid Solution (Length = 187).

Test #23:

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

input:

5 5
00001
11111
01110
01111
01111
1 5 5 2

output:

LRDLLDUDRDLUUDURDDDLLRUDRUUDDLURRLUULUUDULULUDDLLUDRDLULULLRULRDLURLRRDLLRRDLDRDDUURUDUUDDDLLLULUUULDUDRRDRLRLULUDUURLURDDRLRUULDLDUDLULDRURLRDRDRLRURDLULDUDLDLUURLRDDRULRUUDULULRLRDRRDUDLUUULULLLDDDUUDURUUDDRDLDRRLLDRRLRULDRLURLLULULDRDULLDDULULUDUULUULRRULDDUURDURLLDDDRUDUULDRDUDLLDRL

result:

ok Valid Solution (Length = 287).

Test #24:

score: 0
Accepted
time: 995ms
memory: 3832kb

input:

5 5
01011
10111
11011
10101
01110
4 1 2 3

output:

-1

result:

ok No Solution.

Test #25:

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

input:

10 8
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
11111111
7 7 3 6

output:

RUDRLDLULRUUDDDDRRUUUDLRDDRULDLULLLRURRLUURRRDRLLLLLUULDUUURRLULDURDDULDDRLURLURUURUUURUULURDULRRRULRDRRUULDDRURLURRDLLRLUDLURRLRLRDDUDUDRRRDLDRDDLRURRDUDDDLLRUUDLLDLDLRRLRRUDLRUULRLRRULRLRURLRLLULLLRRUDDRLLLUDULRRRRRDLUDDUDRULUDUUUUDLLDRDULULURDLUDLDLLLRLULRURUURLRUUULLRRUULUDDULDRDLLRLUULLDDDRDRUU...

result:

ok Valid Solution (Length = 1343).

Test #26:

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

input:

10 6
111111
101010
111111
101010
111111
101010
111111
101010
111111
101010
1 6 2 3

output:

RRLRLDULRRUDRULRLRDUUULDLRLUUDRULRLUDLLRDRRRLRLUURULRLRURUUUUDRLDRDLUDULUUULDLRRLLDRLLUDRRRDDURUDLLLRLDUDRLDRDLRRLDRDDDULLLRLUDRRUDLLDURDLRULUULRRRRDLDDRLDDRLUDDDURURDDDUUDDDRDDLRUDUDRDRUDLURULDUULDDUUDDRDUDUDUDRDUURRDDUUURRRDLDULRRDUUDULLDULDRRDRUDRULUDLDDLDDRLRLRRDURULLLLLDRRDURLRULULDRLUULRUDDUDR...

result:

ok Valid Solution (Length = 1465).

Test #27:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

10 10
1111111111
1000000000
1111111111
0000000001
1111111111
1000000000
1111111111
0000000001
1111111111
1000000000
5 5 5 2

output:

RLULLLDURDRRRULRLLLLRRLLLLURURLULLLRUDULRRRUDDLRULULULLUDULRRLUDLDULLLRUDDDRULURUULLLLDLDUDDRDURURULRUDLDLLDUDRRLLLRDDLDUDDDUDDDULRURURURLRDRLDLUDLRRRURDURUDDDDURDDRULRURLLRUUDLULULLRRRDUDLULRDDDLUDUDRRUDLRDRUUUDRRRRLUDURRLDRLDLDUULLRRRRDURDLRLURDLRULDUUDLUDDUURRDLDLRURDRUDULRDULULLDLRRLURDRRDURRUUR...

result:

ok Valid Solution (Length = 11109).

Test #28:

score: -100
Time Limit Exceeded

input:

10 10
1010110101
0000011010
1001001001
0011111000
1000111100
1011101001
1100110011
0110001011
0011111000
0101011101
7 5 4 3

output:

-1

result: