QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#395412#7751. Palindrome PathlinweitongWA 0ms3852kbC++203.2kb2024-04-21 14:17:472024-04-21 14:17:48

Judging History

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

  • [2024-04-21 14:17:48]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3852kb
  • [2024-04-21 14:17:47]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m;
char a[35][35];
int sx,sy,ex,ey,b[100000][2],tot,tott,ckk;
bool vis[35][35];
const int dx[4]={0,0,-1,1};
const int dy[4]={1,-1,0,0};
void dfs(int x,int y){
	b[++tot][0]=x,b[tot][1]=y;
	vis[x][y]=1;
	for (int i=0;i<4;++i){
		int xx=x+dx[i],yy=y+dy[i];
		if (xx<1||yy<1||xx>n||yy>m)continue;
		if (a[xx][yy]==48)continue;
		if (!vis[xx][yy]){
			dfs(xx,yy);
			b[++tot][0]=x,b[tot][1]=y;
		}
	}
}
void dfs2(int x,int y){
	b[++tot][0]=x,b[tot][1]=y;
	vis[x][y]=1;
	if (x==ex&&y==ey){
		tott=tot;
		ckk=1;
		return;
	}
	for (int i=0;i<4;++i){
		int xx=x+dx[i],yy=y+dy[i];
		if (xx<1||yy<1||xx>n||yy>m)continue;
		if (a[xx][yy]==48)continue;
		if (!vis[xx][yy]){
			dfs2(xx,yy);
			b[++tot][0]=x,b[tot][1]=y;
		}
	}
}
int tt[5];
char ttt[5]={'U','D','L','R'};
char anss[1000000];int ansl;
void gouzao(int tp,int x,int y){
	for (int i=1;i<=x;++i)anss[++ansl]=ttt[tp];
	for (int i=1;i<=y;++i)anss[++ansl]=ttt[tp^1];
//	anss[++ansl]=' ';
}
void wk(int x,int y,int tp){
	int s=0;
	if (!tp){
		for (int i=x-1;i>=1;--i){
			if (a[i][y]==48)break;
			++s;
		}
	}
	else if (tp==1){
		for (int i=x+1;i<=n;++i){
			if (a[i][y]==48)break;
			++s;
		}
	}
	else if (tp==2){
		for (int i=y-1;i>=1;--i){
			if (a[x][i]==48)break;
			++s;
		}
	}
	else if (tp==3){
		for (int i=y+1;i<=m;++i){
			if (a[x][i]==48)break;
			++s;
		}
	}
	if (s<tt[tp]){
		gouzao(tp,s+1,s+1);
	}
	else{
		gouzao(tp,tt[tp],tt[tp]+1);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;++i)scanf("%s",a[i]+1);
	scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
	for (int i=ex+1;i<=n;++i){
		if (a[i][ey]==48){
			break;
		}
		++tt[0];
	}
	for (int i=ex-1;i>=1;--i){
		if (a[i][ey]==48){
			break;
		}
		++tt[1];
	}
	for (int i=ey+1;i<=m;++i){
		if (a[ex][i]==48){
			break;
		}
		++tt[2];
	}
	for (int i=ey-1;i>=1;--i){
		if (a[ex][i]==48){
			break;
		}
		++tt[3];
	}
	dfs(sx,sy);
	memset(vis,0,sizeof(vis));
	dfs2(sx,sy);
	if (!ckk){
		return cout<<"-1\n",0;
	}
	tot=tott;
	int nowx=sx,nowy=sy;
//	cout<<nowx<<" "<<nowy<<"\n";
	for (int i=2;i<=tot;++i){
//		if (i==12){
//			cout<<"!!!!\n";
//			cout<<nowx<<" "<<nowy<<"\n";
//			cout<<b[i][0]<<" "<<b[i][1]<<"\n"; 
//			cout<<b[i][0]-nowx<<"|n";
//			cout<<"!!!!\n";
//		} 
		if (b[i][0]-nowx==1)wk(nowx,nowy,0);
		if (nowx-b[i][0]==1)wk(nowx,nowy,1);
		if (b[i][1]-nowy==1)wk(nowx,nowy,2);
		if (nowy-b[i][1]==1)wk(nowx,nowy,3);
		nowx=b[i][0],nowy=b[i][1];
//		cout<<nowx<<" "<<nowy<<"\n";
	}
//	cout<<"\n";
	for (int i=1;i<=ansl;++i)cout<<anss[i];
	int u=sx,v=sy;
	for (int i=1;i<=ansl;++i){
		if (anss[i]=='U'&&u>1)--u;
		if (anss[i]=='D'&&u<n)++u;
		if (anss[i]=='L'&&v>1)--v;
		if (anss[i]=='R'&&v<m)++v;
//		cout<<u<<" "<<v<<"\n";
//		if (anss[i]==' '){
//			int ck=0;
//			for (int j=i-1;j>=1;--j){
//				if (anss[j]==' ')break;
//				ck=j;
//			}
//			for (int j=ck;j<=i;++j)cout<<anss[j];
//			cout<<"\n";	
//		}
	}
	for (int i=ansl;i>=1;--i)cout<<anss[i];
//	for (int i=1;i<=tot;++i)a[b[i][0]][b[i][1]]=48;
//	for (int i=1;i<=n;++i){
//		for (int j=1;j<=m;++j){
//			cout<<a[i][j];
//		}
//		cout<<"\n";
//	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3848kb

input:

2 2
11
11
1 1 2 2

output:

RDRLRDURLRDDRLRUDRLRDR

result:

ok Valid Solution (Length = 22).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:


result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

LLRRLLRRRDDUURLRLLRLLDDDUUULRLLRRLLRRRDDDUUUURLRLLRLLLRLLRRLLRRRUDRLRLLRLLUDDUDDUDDLRLLRRLLRRRRLRLLRLLDUDDUULRLLRRLLRRRUDDRLRLLLLRLRDDURRRLLRRLLRLUUDDUDLLRLLRLRRRRLLRRLLRLDDUDDUDDULLRLLRLRDURRRLLRRLLRLLLRLLRLRUUUUDDDRRRLLRRLLRLUUUDDDLLRLLRLRUUDDRRRLLRRLL

result:

ok Valid Solution (Length = 254).

Test #5:

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

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

RDDRLRRLLRRRLLLRRRRLLLLDDDUUUDDDDUUUURRDDDDDUUUURRRLLLRRRRLLLLDDDDRRRRDUDRLRRLLDUDRRRLLLRRRRLLLLDUDDUURRRRDDDUUUDDDDUUUURLRDDRLRRLLRRRLLLRRRRLLLLDDDUUUDDDDUUUURRDDDDDUUUURRRLLLRRRRLLLLDDDDRRRRRRRRDDDDLLLLRRRRLLLRRRUUUUDDDDDRRUUUUDDDDUUUDDDLLLLRRRRLLLRRRLLRRLRDDRLRUUUUDDDDUUUDDDRRRRUUDDUDLLLLRRRRLLLR...

result:

ok Valid Solution (Length = 384).

Test #6:

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

input:

5 3
111
100
111
001
111
4 3 3 2

output:

URLRLLUULRLRRRLRLLDDLRLRRDDRLRLLLRLRRUURLLRUURRLRLLLRLRDDRRLRLDDLLRLRRRLRLUULLRLRU

result:

ok Valid Solution (Length = 82).

Test #7:

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

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

LUUDUUDDRRRUUUDUUDDUUDDDLUUDDURULLLURLUULRULLLURUDDUULDDDUUDDUUDUUURRRDDUUDUUL

result:

ok Valid Solution (Length = 78).

Test #8:

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

input:

5 3
101
111
100
111
100
4 1 2 2

output:

LRLRRRLRLLUULRLRRUDRLRLLUDDDDULRLRRRLRLLUULRRLUULLRLRRRLRLUDDDDULLRLRDURRLRLUULLRLRRRLRL

result:

ok Valid Solution (Length = 88).

Test #9:

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

input:

5 5
01110
10110
11110
11011
11100
2 4 5 1

output:

LDDUULLRRLLLRDDLLRRRDLRLDULLLDDDUUUDDLRDLLRRLLLRDULDDUULRLLRRDULRLDDUULLRRLLLRDDLLRRRDLRLDULLLDDDUUUDDLRDLLRRLLLLRRLLDRLDDUUUDDDLLLUDLRLDRRRLLDDRLLLRRLLUUDDLRLUDRRLLRLUUDDLUDRLLLRRLLDRLDDUUUDDDLLLUDLRLDRRRLLDDRLLLRRLLUUDDL

result:

ok Valid Solution (Length = 222).

Test #10:

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

input:

5 3
011
111
110
111
011
3 1 2 1

output:

LRULLRRULLRUDLLLRUUDDUUDDDLLRRUDLLRULLLRULLRULLRRULLRUDLLLLDURLLURRLLURLLURLLLURLLDURRLLDDDUUDDUURLLLDURLLURRLLURL

result:

ok Valid Solution (Length = 114).

Test #11:

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

input:

4 5
11111
11111
11111
11111
3 2 1 3

output:

LLRRLLRRRLLRRRURLRRLLRRLLLRRLLLULRLLRRLLRRRLLRRRRLRRLLRRLLLRRLLLUDUUDDUUUDDDLRLLRRLLRRRLLRRRRLRRLLRRLLLRRLLLUULRLLRRLLRRRLLRRRUUDDRLRRLLRRLLLLLRRLLRRRLLRRRURLRRLLRRLLLRRLLLULRLLRRRRLLRLULLLRRLLLRRLLRRLRURRRLLRRRLLRRLLLLLRRLLRRLRDDUURRRLLRRRLLRRLLRLUULLLRRLLLRRLLRRLRRRRLLRRRLLRRLLRLDDDUUUDDUUDULLLRRL...

result:

ok Valid Solution (Length = 358).

Test #12:

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

input:

5 5
11111
10101
11111
10101
11111
2 5 1 1

output:

ULLLLUDUUDDLRLLRRLLLRRRLLLLRRRRUUUDDDUUUUDDDDLLLLUUUUUDDDDLRLLRRUUUUUDDDDLLLRRRLLLLRRRRUULLUUUDDLLUULRLLRRLLLRRRLLLLRRRRUDULLLLLLLLUDURRRRLLLLRRRLLLRRLLRLUULLDDUUULLUURRRRLLLLRRRLLLDDDDUUUUURRLLRLDDDDUUUUULLLLDDDDUUUUDDDUUURRRRLLLLRRRLLLRRLLRLDDUUDULLLLU

result:

ok Valid Solution (Length = 254).

Test #13:

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

input:

4 5
11111
10000
11111
00001
1 3 4 5

output:

RRLLLLDDRRRRDDULLLLDUDUURRRRLLLLDDRRRRDDRRRRDDLLLLRRRRUUDUDLLLLUDDRRRRDDLLLLRR

result:

ok Valid Solution (Length = 78).

Test #14:

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

input:

3 5
10100
00010
00111
1 3 1 1

output:

-1

result:

ok No Solution.

Test #15:

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

input:

4 5
10001
11111
11100
11111
4 5 3 1

output:

LLLLDULRLLRRDDUULLRRRLLRRRDUUDLLLLDDUUUUDLRLLRRUDLLUDDLRLLRRLLRRRLLRRRLLLLDUUDLLLLRRRLLRRRLLRRLLRLDDULLDURRLLRLDUUUUDDLLLLDUUDRRRLLRRRLLUUDDRRLLRLUDLLLL

result:

ok Valid Solution (Length = 152).

Test #16:

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

input:

3 5
11111
10100
11111
1 2 3 5

output:

RRRRLRRLLDDRRRLRRLLRRRLLLRRRRLLLLUUDDRRUURRRLLLRRRRLRRLLDDRRRRDDLLRRLRRRRLLLRRRUURRDDUULLLLRRRRLLLRRRLLRRLRRRDDLLRRLRRRR

result:

ok Valid Solution (Length = 120).

Test #17:

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

input:

4 5
01110
10101
11011
10111
1 3 2 3

output:

RLLRDDURLLRDDRLLRUDDRLLR

result:

wrong answer (2,1) Not Visited