QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#395457#7751. Palindrome PathXun_xiaoyaoWA 1ms3772kbC++142.2kb2024-04-21 14:55:522024-04-21 14:55:53

Judging History

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

  • [2024-04-21 14:55:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3772kb
  • [2024-04-21 14:55:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int Qread()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x;
}
int get_ch()
{
	char ch=getchar();
	while(ch!='0'&&ch!='1') ch=getchar();
	return ch=='1';
}
bool fin,vis[40][40],mp[40][40];
int n,m,stx,sty,enx,eny;
char stk[810010];int top;
void dfs(int x,int y)
{
	vis[x][y]=true;
	if(x>1&&mp[x-1][y]&&!vis[x-1][y])
	{
		stk[++top]='U';
		dfs(x-1,y);
		stk[++top]='D';
	}
	if(x<n&&mp[x+1][y]&&!vis[x+1][y])
	{
		stk[++top]='D';
		dfs(x+1,y);
		stk[++top]='U';
	}
	if(y>1&&mp[x][y-1]&&!vis[x][y-1])
	{
		stk[++top]='L';
		dfs(x,y-1);
		stk[++top]='R';
	}
	if(y<m&&mp[x][y+1]&&!vis[x][y+1])
	{
		stk[++top]='R';
		dfs(x,y+1);
		stk[++top]='L';
	}
}
void tkop(int &x,int &y,char op)
{
	if(op=='U'&&x>1&&mp[x-1][y]) x--;
	if(op=='D'&&x<n&&mp[x+1][y]) x++;
	if(op=='L'&&y>1&&mp[x][y-1]) y--;
	if(op=='R'&&y<m&&mp[x][y+1]) y++;
}
bool vid[40][40][40][40];
void calc(int stx,int sty,int enx,int eny)
{
	if(vid[stx][sty][enx][eny]) return;
	vid[stx][sty][enx][eny]=true;
	if(stx==sty&&enx==eny)
	{
		for(int i=1;i<=top;i++) putchar(stk[i]);
		reverse(stk+1,stk+top+1);
		for(int i=1;i<=top;i++) putchar(stk[i]);
		exit(0);
	}
	int x_,y_;

	top++;

	tkop(x_=stx,y_=sty,stk[top]='U');
	if(enx==1||!mp[enx-1][eny]) calc(x_,y_,enx,eny);
	if(enx<n&&mp[enx+1][eny]) calc(x_,y_,enx+1,eny);

	tkop(x_=stx,y_=sty,stk[top]='D');
	if(enx==n||!mp[enx+1][eny]) calc(x_,y_,enx,eny);
	if(enx>1&&mp[enx-1][eny]) calc(x_,y_,enx-1,eny);

	tkop(x_=stx,y_=sty,stk[top]='L');
	if(enx==1||!mp[enx][eny-1]) calc(x_,y_,enx,eny);
	if(eny<m&&mp[enx][eny+1]) calc(x_,y_,enx,eny+1);

	tkop(x_=stx,y_=sty,stk[top]='R');
	if(enx==m||!mp[enx][eny+1]) calc(x_,y_,enx,eny);
	if(enx>1&&mp[enx][eny-1]) calc(x_,y_,enx,eny-1);

	top--;
}
int main()
{
	n=Qread(),m=Qread();
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
		mp[i][j]=get_ch();
	stx=Qread(),sty=Qread(),enx=Qread(),eny=Qread();
	dfs(enx,eny);

	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
		if(mp[i][j]&&!vis[i][j])
			return printf("-1\n"),0;

	reverse(stk+1,stk+top+1);
	for(int i=1;i<=top;i++)
		tkop(stx,sty,stk[i]);
	calc(stx,sty,enx,eny);
	return 0;
}

详细

Test #1:

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

input:

2 2
11
11
1 1 2 2

output:

DRUDLUULDURD

result:

ok Valid Solution (Length = 12).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:


result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

DDDRUUUULLDDDDLUUUUDDDDRUUUURRDDDDLUUUUDDDDDDULUDDDDDUUULDDDDDURUDDDDDUUURDDDDDURRUDDDDDRUUUDDDDDURUDDDDDLUUUDDDDDULUDDDDDDUUUULDDDDRRUUUURDDDDUUUULDDDDLLUUUURDDD

result:

ok Valid Solution (Length = 162).

Test #5:

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

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

DDDDRRUULRUULRRRDDLRDDLRUUUULLDDDDLLUUUUUUUULLDDDDLLUUUURLDDRLDDRRRLUURLUURRDDDD

result:

ok Valid Solution (Length = 80).

Test #6:

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

input:

5 3
111
100
111
001
111
4 3 3 2

output:

LUURRLLDDRRDDLLRRUULLUUUULLUURRLLDDRRDDLLRRUUL

result:

ok Valid Solution (Length = 46).

Test #7:

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

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

UULLULDDDUUURUDDRDURDDUUDDRUDRDDURUUUDDDLULLUU

result:

wrong answer (5,3) Not Visited