QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#402345#7751. Palindrome Pathle0nWA 7ms25980kbC++142.9kb2024-04-30 13:50:172024-04-30 13:50:17

Judging History

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

  • [2024-04-30 13:50:17]
  • 评测
  • 测评结果:WA
  • 用时:7ms
  • 内存:25980kb
  • [2024-04-30 13:50:17]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
int a[35][35], n, m;
bool vis[35][35];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int fa[810005], fe[810005], dis[810005];
char ch[4] = {'R', 'D', 'L', 'U'}, tmp[35];
vector< pair<int, int> > e[810005];
vector<int> wow, owo;
queue<int> q;
int pos(int u, int v, int w, int x)
{
	return ((u - 1) * m + v - 1) * n * m + (w - 1) * m + x;
}
void dfs(int x, int y)
{
	int i;
	vis[x][y] = 1;
	for(i = 0; i < 4; i++)
		if(a[x + dx[i]][y + dy[i]] && !vis[x + dx[i]][y + dy[i]])
		{
			wow.emplace_back(i);
			dfs(x + dx[i], y + dy[i]);
			wow.emplace_back(i ^ 2);
		}
}
void bfs(int p)
{
	int i, h = 0, u, v, w, x, d = -1, len;
	memset(dis, 0x3f, sizeof(dis));
	q.push(p);
	dis[p] = 0;
	while(!q.empty())
	{
		h = q.front();
		q.pop();
		u = (h - 1) / (n * m);
		v = u % m + 1;
		u = u / m + 1;
		w = (h - 1) % (n * m);
		x = w % m + 1;
		w = w / m + 1;
		if(u == w && v == x)
		{
			d = -1;
			break;
		}
		for(i = 0; i < 4; i++)
			if(w == u + dx[i] && x == v + dy[i])
			{
				d = i;
				break;
			}
		if(d != -1)
			break;
		for(auto y: e[h])
			if(dis[y.first] == inf)
			{
				dis[y.first] = dis[h] + 1;
				fa[y.first] = h;
				fe[y.first] = y.second;
				q.push(y.first);
			}
	}
	while(fe[h])
	{
		owo.emplace_back(fe[h]);
		h = fa[h];
	}
	reverse(owo.begin(), owo.end());
	for(auto o: owo)
		wow.emplace_back(o);
	len = 2 * wow.size() + (d != -1);
	if(d != -1)
		wow.emplace_back(d);
	for(i = 0; i < len; i++)
		printf("%c", ch[wow[min(i, len - i - 1)]]);
	printf("\n");
}

int main()
{
	int i, j, k, l, o, p, q, sx, sy, ex, ey, t;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++)
	{
		scanf("%s", tmp + 1);
		for(j = 1; j <= m; j++)
			a[i][j] = tmp[j] - '0';
	}
	o = 0;
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			o += a[i][j];
	if(o == 1)
	{
		printf("\n");
		return 0;
	}
	scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			for(k = 1; k <= n; k++)
				for(l = 1; l <= n; l++)
				{
					p = pos(i, j, k, l);
					for(o = 0; o < 4; o++)
					{
						t = a[i + dx[o]][j + dy[o]];
						if(a[k - dx[o]][l - dy[o]])
						{
							q = pos(i + dx[o] * t, j + dy[o] * t, k - dx[o], l - dy[o]);
							e[p].emplace_back(make_pair(q, o));
						}
						if(!a[k + dx[o]][l + dy[o]])
						{
							q = pos(i + dx[o] * t, j + dy[o] * t, k, l);
							e[p].emplace_back(make_pair(q, o));
						}
					}
				}
	dfs(ex, ey);
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
			if(a[i][j] && !vis[i][j])
			{
				printf("-1\n");
				return 0;
			}
	reverse(wow.begin(), wow.end());
	for(i = 0; i < wow.size(); i++)
	{
		o = a[sx + dx[wow[i]]][sy + dy[wow[i]]];
		sx += o * dx[wow[i]];
		sy += o * dy[wow[i]];
	}
	bfs(pos(sx, sy, ex, ey));
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 25804kb

input:

2 2
11
11
1 1 2 2

output:

RDLRULDLURLDR

result:

ok Valid Solution (Length = 13).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

score: 0
Accepted
time: 4ms
memory: 22788kb

input:

1 1
1
1 1 1 1

output:



result:

ok Valid Solution (Length = 0).

Test #4:

score: 0
Accepted
time: 3ms
memory: 25940kb

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

LLURRRDDLLLDRRRDLLLRRRULLLURRRUULLLDRRDLDRRDLLLUURRRULLLURRRLLLDRRRDLLLDDRRRULL

result:

ok Valid Solution (Length = 79).

Test #5:

score: 0
Accepted
time: 3ms
memory: 25980kb

input:

5 5
11111
10101
11111
10101
11111
1 4 5 5

output:

RRRRDDLLUDLLDDRRRRUDLLUDLLUUUDRRRRUULLLLDDDDLLLLUURRRRDUUULLDULLDURRRRDDLLDULLDDRRRR

result:

ok Valid Solution (Length = 84).

Test #6:

score: 0
Accepted
time: 3ms
memory: 25872kb

input:

5 3
111
100
111
001
111
4 3 3 2

output:

RDDLLRRUULLUURRLLDDRRDDLLRRUULLUURRLLDDR

result:

ok Valid Solution (Length = 40).

Test #7:

score: 0
Accepted
time: 7ms
memory: 25844kb

input:

5 4
1001
1101
1111
0011
0010
2 2 1 1

output:

ULURLLLDDUUURUDLDRRDRDUUUUUDRDRRDLDURUUUDDLLLRULU

result:

ok Valid Solution (Length = 49).

Test #8:

score: -100
Wrong Answer
time: 7ms
memory: 25972kb

input:

5 3
101
111
100
111
100
4 1 2 2

output:

RDUUUUDLLRRDDLLDURLUURUULRUDLLDDRRLLDUUUUDR

result:

wrong answer (1,3) Not Visited