QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#310528#7751. Palindrome PathA_programmerWA 0ms3832kbC++172.3kb2024-01-21 15:12:122024-01-21 15:12:13

Judging History

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

  • [2024-01-21 15:12:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3832kb
  • [2024-01-21 15:12:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

int n, m, sx, sy, ex, ey, cnt;
bool a[35][35], vis[35][35];
int lst[35][35];
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
char ans[1000005];

queue<int> q;
void dfs(int x, int y)
{
	vis[x][y] = 1;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		if (a[nx][ny] || vis[nx][ny]) continue;
		q.push(i);
		lst[nx][ny] = 3 - i;
		dfs(nx, ny);
		q.push(3 - i);
	}
}

void find(int x, int y)
{
	if (x == sx && y == sy) return;
	find(x + dx[lst[x][y]], y + dy[lst[x][y]]);
	q.push(3 - lst[x][y]);
}

void work(int x, int y, int op)
{
	int nx = ex, ny = ey, nw = 0;
	if (op == 0)
	{
		while (!a[x][y - 1] && !a[nx][ny + 1]) x--, nx++, ans[++cnt] = 'L', nw++;
		if (a[nx][ny + 1]) ans[++cnt] = 'R';
		else ans[++cnt] = 'L', ans[++cnt] = 'R';
		for (int i = 1; i <= nw; i++) ans[++cnt] = 'R';
	}
	else if (op == 1)
	{
		while (!a[x - 1][y] && !a[nx + 1][ny]) y--, ny++, ans[++cnt] = 'U', nw++;
		if (a[nx + 1][ny]) ans[++cnt] = 'D';
		else ans[++cnt] = 'U', ans[++cnt] = 'D';
		for (int i = 1; i <= nw; i++) ans[++cnt] = 'D';
	}
	else if (op == 2)
	{
		while (!a[x + 1][y] && !a[nx - 1][ny]) y++, ny--, ans[++cnt] = 'D', nw++;
		if (a[nx - 1][ny]) ans[++cnt] = 'U';
		else ans[++cnt] = 'D', ans[++cnt] = 'U';
		for (int i = 1; i <= nw; i++) ans[++cnt] = 'U';
	}
	else
	{
		while (!a[x][y + 1] && !a[nx][ny - 1]) x++, nx--, ans[++cnt] = 'R', nw++;
		if (a[nx][ny - 1]) ans[++cnt] = 'L';
		else ans[++cnt] = 'R', ans[++cnt] = 'L';
		for (int i = 1; i <= nw; i++) ans[++cnt] = 'L';
	}
}

int main()
{	
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		char s[35];
		cin >> s + 1;
		for (int j = 1; j <= m; j++) a[i][j] = s[j] ^ '1';
	}
	for (int i = 0; i <= n + 1; i++) a[i][0] = a[i][m + 1] = 1;
	for (int i = 0; i <= m + 1; i++) a[0][i] = a[n + 1][i] = 1;
	
	cin >> sx >> sy >> ex >> ey;
	dfs(sx, sy);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (!a[i][j] && !vis[i][j])
			{
				cout << "-1";
				return 0;
			}
	find(ex, ey);
	
	while (q.size())
	{
		work(sx, sy, q.front());
		sx += dx[q.front()], sy += dy[q.front()];
		q.pop();
	}
	for (int i = 1; i <= cnt; i++) cout << ans[i];
	for (int i = cnt; i; i--) cout << ans[i];
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:


result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

LLRRRLLRRRUUUDDDDRLRRLLRRLLDUDDUUULRLLRRRLLRRRDDUUDDUURLUDRRRRLLLLLDDUUURRRRLLLLLUDDDUUULRUDLLRRRDDUUULLRRUDUUUDDDDRLRRRRLLLLRRRRLLLLUUDDUUDDLRLLRRRLLRRRDURLRRRLLLLLLRRRLRUDRRRLLRRRLLRLDDUUDDUULLLLRRRRLLLLRRRRLRDDDDUUUDURRLLUUUDDRRRLLDURLUUUDDDULLLLLRRRRUUUDDLLLLLRRRRDULRUUDDUUDDRRRLLRRRLLRLUUUDDUDL...

result:

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