QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#688716#7751. Palindrome Pathicpc_zhzx034WA 0ms3648kbC++142.5kb2024-10-30 12:56:162024-10-30 12:56:16

Judging History

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

  • [2024-10-30 12:56:16]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3648kb
  • [2024-10-30 12:56:16]
  • 提交

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=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,100000)
	{
		if(cnt==n*m&&Abs(nsx-nfx)+Abs(nsy-nfy)<=1)
		{
			rep(i,0,p-2)
				cout<<t[i];
			if(nsx>nfx)
				cout<<'L';
			if(nsx<nfx)
				cout<<'R';
			if(nsy>nfy)
				cout<<'U';
			if(nsy<nfy)
				cout<<'D';
			rep_(i,p-2,0)
				cout<<t[i];
			cout<<'\n';
			exit(0);
		}
		int 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];
		if(val(nfx+dx[dir],nfy+dy[dir]))
			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;
	if(sx==fx&&sy==fy)
	{
		cout<<'\n';
		return;
	}
	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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3648kb

input:

2 2
11
11
1 1 2 2

output:

URDRDLLDRDRU

result:

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