QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#773107#7751. Palindrome PathCrysflyTL 3ms21640kbC++143.1kb2024-11-23 01:01:082024-11-23 01:01:09

Judging History

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

  • [2024-11-23 01:01:09]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:21640kb
  • [2024-11-23 01:01:08]
  • 提交

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
*/

Details

Tip: Click on the bar to expand more detailed information

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

output:


result: