QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#291386#7751. Palindrome PathPhantomThresholdWA 1ms3592kbC++202.1kb2023-12-26 14:35:492023-12-26 14:35:50

Judging History

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

  • [2023-12-26 14:35:50]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3592kb
  • [2023-12-26 14:35:49]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int maxn=30;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
const char dch[]="DRUL";

vector<int> ans;

int n,m;
int a[maxn+5][maxn+5];
int mxdir[4][maxn+5][maxn+5];
int vis[maxn+5][maxn+5];
int nxt[maxn+5][maxn+5];
int sx,sy,ex,ey;

void dfs(int x,int y){
//	cerr << "dfs : " << x << " " << y << endl;
	vis[x][y]=1;
	for (int k=0;k<4;k++){
		int nx=x+dx[k];
		int ny=y+dy[k];
		if (a[nx][ny]==0 || vis[nx][ny]==1) continue;
		ans.push_back(k^2);
		nxt[nx][ny]=k^2;
		dfs(nx,ny);
		ans.push_back(k);
	}
}
void solve(int x,int y){
	if (x==ex && y==ey) return;
	int k=nxt[x][y];
	int L=min(mxdir[k^2][x][y],mxdir[k][ex][ey]);
	
	if (L==mxdir[k][ex][ey]){
		for (int t=1;t<=L;t++) ans.push_back(k^2);
		for (int t=1;t<=L+1;t++) ans.push_back(k);
	}
	else{
		for (int t=1;t<=L+1;t++) ans.push_back(k^2);
		for (int t=1;t<=L+1;t++) ans.push_back(k);
	}
	solve(x+dx[k],y+dy[k]);
}

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i=1;i<=n;i++){
		string str;
		cin >> str;
		for (int j=1;j<=m;j++) a[i][j]=str[j-1]-'0';	
	}
	cin >> sx >> sy >> ex >> ey;
	
	for (int k=0;k<4;k++){
		for (int i=1;i<=n;i++){
			for (int j=1;j<=m;j++){
				for (int L=0;L<=max(n,m);L++){
					if (a[i+dx[k]*L][j+dy[k]*L]==0) break;
					mxdir[k][i][j]=L;	
				}
			}
		}
	}
	dfs(ex,ey);
	/*
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			cout << dch[nxt[i][j]] << " ";
		}
		cout << endl;
	}
	for (int k=0;k<4;k++){
		for (int i=1;i<=n;i++){
			for (int j=1;j<=m;j++){
				cout << mxdir[k][i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
	*/
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (a[i][j] && !vis[i][j]){
				cout << "-1" << "\n";
				return 0;	
			}
		}
	}
	for (auto k:ans){
		int nx=sx+dx[k];
		int ny=sy+dy[k];
		if (a[nx][ny]==1){
			nx=sx;
			ny=sy;
		}
	}
	
	solve(sx,sy);
	
	int sz=ans.size();
	for (int i=0;i<=sz-1;i++) cout << dch[ans[i]];
	for (int i=sz-1;i>=0;i--) cout << dch[ans[i]];
	cout << "\n";
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3472kb

input:

2 2
11
11
1 1 2 2

output:

DRUDLURDDRULDURD

result:

ok Valid Solution (Length = 16).

Test #2:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: 0
Accepted
time: 0ms
memory: 3468kb

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

ULLDDDDRUUUDRDDRUUUUDDDDLUULDDLUUUURRDDRRUUUULDDLUULDDDDUUUURDDRDUUURDDDDLLU

result:

ok Valid Solution (Length = 76).

Test #5:

score: 0
Accepted
time: 0ms
memory: 3476kb

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

DDDDRRUUUULRRRDDLRDDLRUUUULLDDLRDDLLUUUURDDDDDDDDRUUUULLDDRLDDLLUUUURLDDRLDDRRRLUUUURRDDDD

result:

ok Valid Solution (Length = 90).

Test #6:

score: 0
Accepted
time: 0ms
memory: 3512kb

input:

5 3
111
100
111
001
111
4 3 3 2

output:

LUURRLLDDRRDDLLRRUULURLLRULUURRLLDDRRDDLLRRUUL

result:

ok Valid Solution (Length = 46).

Test #7:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

UULLUUDLDDDUUURDRDURDDUDLUUUULDUDDRUDRDRUUUDDDLDUULLUU

result:

ok Valid Solution (Length = 54).

Test #8:

score: -100
Wrong Answer
time: 0ms
memory: 3584kb

input:

5 3
101
111
100
111
100
4 1 2 2

output:

LDURRUUUDLLRRDDDULUULRRLUULUDDDRRLLDUUURRUDL

result:

wrong answer (1,1) Not Visited