QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#394890#7751. Palindrome PathlinweitongWA 1ms3848kbC++202.3kb2024-04-20 21:22:162024-04-20 21:22:17

Judging History

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

  • [2024-04-20 21:22:17]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3848kb
  • [2024-04-20 21:22:16]
  • 提交

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];
}
void wk(int x,int y,int tp){
	int s=0;
	if (!tp){
		for (int i=x-1;i>=1;--i){
			if (a[i][ey]==48)break;
			++s;
		}
	}
	else if (tp==1){
		for (int i=x+1;i<=n;++i){
			if (a[i][ey]==48)break;
			++s;
		}
	}
	else if (tp==2){
		for (int i=y-1;i>=1;--i){
			if (a[ex][i]==48)break;
			++s;
		}
	}
	else if (tp==3){
		for (int i=y+1;i<=m;++i){
			if (a[ex][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;
	for (int i=2;i<=tot;++i){
		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];
	}
	for (int i=1;i<=ansl;++i)cout<<anss[i];
	for (int i=ansl;i>=1;--i)cout<<anss[i];
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3840kb

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: 3848kb

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: 1ms
memory: 3760kb

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: 3844kb

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: 3768kb

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

LUUDUUDDRRRUUUDUUDDUUDDDLUUDDDURULLLURLUULRULLLURUDDDUULDDDUUDDUUDUUURRRDDUUDUUL

result:

ok Valid Solution (Length = 80).

Test #8:

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

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: 3712kb

input:

5 5
01110
10110
11110
11011
11100
2 4 5 1

output:

LDDDUUUULLRRRLLLLRRDDLLRRRDLLRRRLDDUULLLDDDUUUDDLRDLLRRLLLRDULDDUULRLLRRDDDUUULLRRRLDDDUUUULLRRRLLLLRRDDLLRRRDLLRRRLDDUULLLDDDUUUDDLRDLLRRLLLLRRLLDRLDDUUUDDDLLLUUDDLRRRLLDRRRLLDDRRLLLLRRRLLUUUUDDDLRRRLLUUUDDDRRLLRLUUDDLUDRLLLRRLLDRLDDUUUDDDLLLUUDDLRRRLLDRRRLLDDRRLLLLRRRLLUUUUDDDL

result:

ok Valid Solution (Length = 280).

Test #10:

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

input:

5 3
011
111
110
111
011
3 1 2 1

output:

LRULLRRULLLRRUDLLLRUDUUDDLLRRUUDDDLLLRRULLLRULLRULLRRULLLRRUDLLLLDURRLLLURRLLURLLURLLLURRLLLDDDUURRLLDDUUDURLLLDURRLLLURRLLURL

result:

wrong answer (5,2) Not Visited