QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#688790 | #7751. Palindrome Path | icpc_zhzx034 | TL | 827ms | 3968kb | C++14 | 2.7kb | 2024-10-30 13:35:07 | 2024-10-30 13:35:08 |
Judging History
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