QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#688790#7751. Palindrome Pathicpc_zhzx034TL 827ms3968kbC++142.7kb2024-10-30 13:35:072024-10-30 13:35:08

Judging History

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

  • [2024-10-30 13:35:08]
  • 评测
  • 测评结果:TL
  • 用时:827ms
  • 内存:3968kb
  • [2024-10-30 13:35:07]
  • 提交

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;
	vis[sx][sy]=1,vis[fx][fy]=1,t="";
	int nsx=sx,nsy=sy,nfx=fx,nfy=fy;
	rep(p,1,50000)
	{
		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=400;
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
11
11
1 1 2 2

output:

RRDLURLDLRULDRR

result:

ok Valid Solution (Length = 15).

Test #2:

score: 0
Accepted
time: 827ms
memory: 3968kb

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: 3820kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

ULRDDURLRUDDULDLDLLUUDLURDDDDDDDRDRRUUDRRRRRLRUURLDRRLLLULUUDDLRURURLDDUULULLLRRDLRUURLRRRRRDUURRDRDDDDDDDRULDUULLDLDLUDDURLRUDDRLU

result:

ok Valid Solution (Length = 131).

Test #5:

score: -100
Time Limit Exceeded

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

-1

result: