QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#269914#7751. Palindrome PathFISHER_WA 0ms3768kbC++141.4kb2023-11-30 11:17:532023-11-30 11:17:54

Judging History

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

  • [2023-11-30 11:17:54]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3768kb
  • [2023-11-30 11:17:53]
  • 提交

answer

#include <bits/stdc++.h>
#define PB push_back
#define EB emplace_back
using namespace std;
const int maxn = 30;
int n, m;
int sx, sy, ex, ey;
char mp[maxn + 5][maxn + 5];
const int d[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
bool vis[maxn + 5][maxn + 5];
inline bool chk(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= m && mp[x][y] == '1' && !vis[x][y]; }
vector<char> op;
inline void mv(int x, int y, int dir) {
	int k = 0;
	int x2 = ex, y2 = ey;
	while (1) {
		x += d[dir ^ 1][0], y += d[dir ^ 1][1];
		x2 += d[dir][0], y2 += d[dir][1];
		if (!chk(x, y) || !chk(x2, y2)) break;
		op.PB("RLDU"[dir]), k++;
	}
	if (!chk(x, y) && chk(x2, y2)) op.PB("RLDU"[dir]);
	for (int i = 1; i <= k + 1; i++) op.PB("LRUD"[dir]);
}
vector<int> r;
void dfs(int x, int y) {
	vis[x][y] = 1;
	for (int dir = 0; dir < 4; dir++) {
		int tx = x + d[dir][0], ty = y + d[dir][1];
		if (chk(tx, ty)) {
			if (!vis[ex][ey]) r.PB(dir);
			mv(x, y, dir);
			dfs(tx, ty);
			mv(tx, ty, dir ^ 1);
			if (!vis[ex][ey]) r.pop_back();
		}
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%s", mp[i] + 1);
	scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
	dfs(sx, sy);
	if (!vis[ex][ey]) return puts("-1"), 0;
	for (int x : r) {
		mv(sx, sy, x);
		sx += d[x][0], sy += d[x][1];
	}
	if (!op.empty()) {
		printf("%s", op.begin());
		reverse(op.begin(), op.end());
		printf("%s", op.begin());
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
11
11
1 1 2 2

output:

RDRLRULRDDRLURLRDR

result:

ok Valid Solution (Length = 18).

Test #2:

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:


result:

ok Valid Solution (Length = 0).

Test #4:

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

input:

5 4
1111
1111
1111
1111
1111
4 2 4 2

output:

RLLDDUULRLRLRULLLULRLRLRLLLUDLRLRLRUDUDLUDLLRRRLURULLLDRRDLLLURULRRRLLDULDUDURLRLRLDULLLRLRLRLULLLURLRLRLUUDDLLR

result:

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