QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#773107 | #7751. Palindrome Path | Crysfly | TL | 3ms | 21640kb | C++14 | 3.1kb | 2024-11-23 01:01:08 | 2024-11-23 01:01:09 |
Judging History
answer
// what is matter? never mind.
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,popcnt,abm,mmx,avx,avx2")
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define ll __int128
//#define ull unsigned long long
#define int long long
#define SZ(x) ((int)((x).size()))
#define ALL(x) (x).begin(),(x).end()
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<ll,ll>pii;
typedef vector<int>vi;
#define maxn 500005
#define inf 0x3f3f3f3f
int n,m,sx,sy,tx,ty;
int a[33][33];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
string opt="DRUL";
bool vs[33][33];
string res;
void mov(int d){
res+=opt[d];
if(a[sx+dx[d]][sy+dy[d]]) sx+=dx[d],sy+=dy[d];
}
void dfs(int x,int y){
vs[x][y]=1;
For(d,0,3){
int xx=x+dx[d],yy=y+dy[d];
if(a[xx][yy] && !vs[xx][yy]) {
mov(d^2);
dfs(xx,yy);
mov(d);
}
}
}
mt19937_64 rnd(64);
int dis[33][33][33][33];
array<int,4> pre[33][33][33][33];
int pres[33][33][33][33];
vector<pii>get(int i,int j,int d){
vector<pii>res;
if(!a[i+dx[d]][j+dy[d]]) res.pb({i,j});
if(a[i-dx[d]][j-dy[d]]) res.pb({i-dx[d],j-dy[d]});
return res;
}
void out(int x1,int y1,int x2,int y2) {
vi qwq;
while(dis[x1][y1][x2][y2]!=0){
int d=pres[x1][y1][x2][y2];
qwq.pb(d);
auto [xx1,yy1,xx2,yy2]=pre[x1][y1][x2][y2];
x1=xx1,y1=yy1,x2=xx2,y2=yy2;
}
reverse(qwq.begin(),qwq.end());
for(auto it:qwq) mov(it);
string rev=res;
reverse(rev.begin(),rev.end());
cout<<res+rev<<"\n";
exit(0);
}
void work()
{
n=read(),m=read();
For(i,1,n){
string s;cin>>s;
For(j,1,m)a[i][j]=(s[j-1]&1);
}
sx=read(),sy=read(),tx=read(),ty=read();
dfs(tx,ty);
For(i,1,n)For(j,1,m){
if(a[i][j] && !vs[i][j]){
puts("-1");
exit(0);
}
}
memset(dis,-1,sizeof dis);
dis[sx][sy][tx][ty]=0;
pres[sx][sy][tx][ty]=-1;
queue<array<int,4>>q;
q.push({sx,sy,tx,ty});
while(q.size()) {
auto [x1,y1,x2,y2]=q.front(); q.pop();
if(x1==x2 && y1==y2){
out(x1,x2,y1,y2);
}
For(d,0,3){
int nx1=x1,ny1=y1;
if(a[nx1+dx[d]][ny1+dy[d]]) nx1+=dx[d],ny1+=dy[d];
vector<pii>o2=get(x2,y2,d);
for(auto [nx2,ny2]:o2){
if(dis[nx1][ny1][nx2][ny2]==-1){
dis[nx1][ny1][nx2][ny2]=dis[x1][y1][x2][y2]+1;
pre[nx1][ny1][nx2][ny2]={x1,y1,x2,y2};
pres[nx1][ny1][nx2][ny2]=d;
q.push({nx1,ny1,nx2,ny2});
}
}
}
}
puts("-1");
}
/*
*/
signed main()
{
// freopen("my.out","w",stdout);
int T=1;
while(T--)work();
return 0;
}
/*
9 30
111111111111111111111111111111
100000000000000000000000000000
111111111111111111111111111111
000000000000000000000000000001
111111111111111111111111111111
100000000000000000000000000000
111111111111111111111111111111
000000000000000000000000000001
111111111111111111111111111111
1 1 9 30
*/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 17024kb
input:
2 2 11 11 1 1 2 2
output:
DRUDLUDRRDULDURD
result:
ok Valid Solution (Length = 16).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 3ms
memory: 14496kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 20508kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
ULLDDDDRUUUDRDDRUUUUDDDDLUULDDLUUUURRDDDDUUUUDDDDRRUUUULDDLUULDDDDUUUURDDRDUUURDDDDLLU
result:
ok Valid Solution (Length = 86).
Test #5:
score: 0
Accepted
time: 0ms
memory: 21640kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
DDDDRRUUUULRRRDDLRDDLRUUUULLDDLRDDLLUUUUDDRRRRDDUUUULLDDRLDDLLUUUURLDDRLDDRRRLUUUURRDDDD
result:
ok Valid Solution (Length = 88).
Test #6:
score: -100
Time Limit Exceeded
input:
5 3 111 100 111 001 111 4 3 3 2