QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#270092#7751. Palindrome Pathtime_interspace#WA 0ms3872kbC++202.2kb2023-11-30 15:14:322023-11-30 15:14:34

Judging History

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

  • [2023-11-30 15:14:34]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3872kb
  • [2023-11-30 15:14:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 35, M = 1e6 + 5;
int n, m, sr, sc, er, ec;
int tot, ans[M];
char ch[N][N];
bool used[N][N];
int fx[4] = {-1, 0, 1, 0}, fy[4] = {0, -1, 0, 1};
int dis[N][N][4];
void predfs(int x, int y)
{
	used[x][y] = 1;
	for (int i = 0; i < 4; i++)
	{
		int u = x + fx[i], v = y + fy[i];
		if (ch[u][v] == '1' && !used[u][v]) predfs(u, v);
	}
}
void init()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (ch[i][j] != '1') continue;
			for (int k = 0; k < 4; k++)
			{
				int cur = 0;
				while (ch[i + fx[k] * (cur + 1)][j + fy[k] * (cur + 1)] == '1')
				{
					cur++;
				}
				dis[i][j][k] = cur;
			}
		}
}
bool check()
{
	predfs(sr, sc);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (ch[i][j] == '1' && !used[i][j]) return 1;
		}
	return 0;
}
bool isend;
void mv(int x, int y, int i)
{
	int j = (i + 2) % 4;
	if (dis[x][y][j] < dis[er][ec][i])
	{
		for (int k = 1; k <= dis[x][y][j]; k++) ans[++tot] = j;
		for (int k = 1; k <= dis[x][y][j] + 1; k++) ans[++tot] = i;
	}
	else
	{
		for (int k = 1; k <= dis[er][ec][i]; k++) ans[++tot] = j;
		for (int k = 1; k <= dis[er][ec][i] + 1; k++) ans[++tot] =i;
	}
}
void dfs(int x, int y, int fl)
{
	used[x][y] = 1;
	if (fl && x == er && y == ec)
	{
		isend = 1;
		return;
	}
	for (int i = 0; i < 4; i++)
	{
		int u = x + fx[i], v = y + fy[i];
		if (ch[u][v] != '1' || used[u][v]) continue;
		mv(x, y, i);
		dfs(u, v, fl);
		mv(u, v, (i + 2) % 4);
		if (isend) return;
	}
}
void write(int x)
{
	if (x == 0) putchar('U');
	if (x == 1) putchar('L');
	if (x == 2) putchar('D');
	if (x == 3) putchar('R');
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%s", ch[i] + 1);
	scanf("%d%d%d%d", &sr, &sc, &er, &ec);
	if (check())
	{
		puts("-1");
		return 0;
	}
	init();
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) used[i][j] = 0;
	dfs(sr, sc, 0);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) used[i][j] = 0;
	dfs(sr, sc, 1);
	for (int i = 1; i <= tot; i++) write(ans[i]);
	for (int i = tot; i; i--) write(ans[i]);
	puts("");
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
11
11
1 1 2 2

output:

DRUDLUDRLUULRDULDURD

result:

ok Valid Solution (Length = 20).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

DUUDDUUUDDDUUUURLLDUDDUDDUDDRLRRUDUUDDUUUDDDUUUULLRRRDUDDUDDUDDUDUUDDUUUDDDUUUULDUDDUDDUDDRLLRLLUDUUDDUUUDDDUUUURDUDDUDDDDUDDUDRUUUUDDDUUUDDUUDULLRLLRDDUDDUDDUDLUUUUDDDUUUDDUUDUDDUDDUDDUDRRRLLUUUUDDDUUUDDUUDURRLRDDUDDUDDUDLLRUUUUDDDUUUDDUUD

result:

wrong answer End Point Is (2,3), Not (er = 4, ec = 2)