QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#1084#291388#7751. Palindrome Pathicpc_zhzx034PhantomThresholdFailed.2024-10-30 14:32:292024-10-30 14:32:29

Details

Extra Test:

Invalid Input

input:

30 30
111111111111111111111111111111
110000000000000000000000000011
101111111111111111111111111101
101111111111111111111111111101
100111111111111111111111111101
101111111111111111111111111101
101011111111111111111111111101
101011111111111111111111111101
101100000000000000000000000011
101011111111111...

output:


result:

FAIL (sr, sc) should be blank

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#291388#7751. Palindrome PathPhantomThresholdAC ✓1ms3748kbC++202.2kb2023-12-26 14:43:512023-12-26 14:43:51

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;
	}
	{
		int sz=ans.size();
		for (int i=0;i<=sz-1;i++) cout << dch[ans[i]];	
		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){
			sx=nx;
			sy=ny;
		}
	}
	
	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;
}