QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#269912 | #7751. Palindrome Path | FISHER_ | WA | 0ms | 3816kb | C++14 | 1.4kb | 2023-11-30 11:15:18 | 2023-11-30 11:15:20 |
Judging History
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]);
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: 3736kb
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: 3816kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3792kb
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)