QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#269908#7751. Palindrome PathFISHER_WA 1ms3796kbC++141.3kb2023-11-30 11:13:572023-11-30 11:13:57

Judging History

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

  • [2023-11-30 11:13:57]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3796kb
  • [2023-11-30 11:13:57]
  • 提交

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) op.PB("LRUD"[x]);
	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: 1ms
memory: 3796kb

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

input:

2 2
10
01
1 1 2 2

output:

-1

result:

ok No Solution.

Test #3:

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

input:

1 1
1
1 1 1 1

output:

(null)(null)

result:

wrong answer Line [name=User Output] equals to "(null)(null)", doesn't correspond to pattern "-1|[LRUD]{0,1000000}"