QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394426 | #7751. Palindrome Path | oscaryang | WA | 2ms | 9880kb | C++17 | 3.3kb | 2024-04-20 14:39:35 | 2024-04-20 14:39:36 |
Judging History
answer
#include<bits/stdc++.h>
#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define lep(i, a, b) for(int i = (a); i >= (b); --i)
using namespace std;
bool st;
mt19937 gen(time(0));
inline int read() {
int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x;
}
const int N = 35;
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
// R L D U
int n, m, sx, sy, tx, ty, tot, cnt, vis[N][N];
int f[N][N][N][N], g[N][N][N][N];
pii s[N][N][N][N], t[N][N][N][N];
struct node { int x, y, u, v; };
char a[N][N], CH[4];
vc <int> S;
vc <char> ans;
inline int ok (int x, int y) { return x > 0 && x <= n && y > 0 && y <= m && a[x][y] == '1'; }
inline int same (int x, int y, int u, int v) { return x == u && y == v; }
inline int adj (int x, int y, int u, int v) { return (x == u && abs (y - v) == 1) || (y == v && abs (x - u) == 1); }
inline void to (int &x, int &y, int i) {
int u = x + dx[i], v = y + dy[i];
if (ok (u, v)) x = u, y = v;
}
inline void dfs (int x, int y, int &X, int &Y) {
vis[x][y] = 1; ++ cnt;
rep (i, 0, 3) {
int u = x + dx[i ^ 1], v = y + dy[i ^ 1];
if (!ok (u, v) || vis[u][v] ) continue;
S.pb (i); to (X, Y, i);
dfs (u, v, X, Y);
S.pb (i ^ 1); to (X, Y, i ^ 1);
}
}
inline void construct (int x, int y, int u, int v) {
vc <int> res; int mid = -1;
if (!same (x, y, u, v)) {
if (x == u) mid = y < v ? 0 : 1;
else mid = x < u ? 2 : 3;
}
while (!same (x, y, sx, sy) || !same (u, v, tx, ty)) {
res.pb (g[x][y][u][v]);
auto [a, b] = s[x][y][u][v];
auto [c, d] = t[x][y][u][v];
x = a; y = b; u = c; v = d;
}
reverse (res.begin (), res.end ());
for (auto u : res) S.pb (u);
for (auto u : S) ans.pb (CH[u]);
if (mid != -1) ans.pb (CH[mid]);
reverse (S.begin (), S.end ());
for (auto u : S) ans.pb (CH[u]);
}
inline void bfs () {
queue <node> Q;
Q.push (node {sx, sy, tx, ty});
f[sx][sy][tx][ty] = 1;
while (!Q.empty ()) {
auto [x, y, u, v] = Q.front (); Q.pop ();
if (same (x, y, u, v) || adj (x, y, u, v)) return construct (x, y, u, v);
rep (i, 0, 3) {
int a, b, c, d;
if (ok (a = u + dx[i ^ 1], b = v + dy[i ^ 1])) {
to (c = x, d = y, i);
if (!f[c][d][a][b]) {
f[c][d][a][b] = 1;
g[c][d][a][b] = i;
s[c][d][a][b] = mkp (x, y);
t[c][d][a][b] = mkp (u, v);
Q.push (node {c, d, a, b});
}
}
if (!ok (a = u + dx[i], b = v + dy[i])) {
to (c = x, d = y, i);
if (!f[c][d][a][b]) {
f[c][d][a][b] = 1;
g[c][d][a][b] = i;
s[c][d][a][b] = mkp (x, y);
t[c][d][a][b] = mkp (u, v);
Q.push (node {c, d, a, b});
}
}
}
}
}
bool ed;
signed main() {
cerr << (&ed - &st) / 1024 / 1024 << "MB ---------------------------" << endl;
CH[0] = 'R', CH[1] = 'L'; CH[2] = 'D'; CH[3] = 'U';
n = read (); m = read ();
rep (i, 1, n) scanf ("%s", a[i] + 1);
rep (i, 1, n) rep (j, 1, m) tot += a[i][j] == '1';
sx = read (); sy = read (); tx = read (); ty = read ();
dfs (tx, ty, sx, sy);
if (cnt < tot) return puts ("-1"), 0;
bfs ();
for (auto u : ans) putchar (u); putchar (10);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 6140kb
input:
2 2 11 11 1 1 2 2
output:
RDLRULRRDRRLURLDR
result:
ok Valid Solution (Length = 17).
Test #2:
score: 0
Accepted
time: 1ms
memory: 3692kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 1ms
memory: 5736kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 2ms
memory: 9880kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
RDLLLDRRRDLLLRRRULLLUURURRLLLRDLDRRRULDLDLURRRDLDRLLLRRURUULLLURRRLLLDRRRDLLLDR
result:
ok Valid Solution (Length = 79).
Test #5:
score: 0
Accepted
time: 1ms
memory: 6068kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
RRRRDDLLLLDDRRRRUDLLUDLLUUUDRRUDRRUULLLLRRDDDDRRLLLLUURRDURRDUUULLDULLDURRRRDDLLLLDDRRRR
result:
ok Valid Solution (Length = 88).
Test #6:
score: 0
Accepted
time: 0ms
memory: 5864kb
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: 1ms
memory: 5928kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
ULURLLLDDUUURUDLDRRDRDULULULUDRDRRDLDURUUUDDLLLRULU
result:
ok Valid Solution (Length = 51).
Test #8:
score: -100
Wrong Answer
time: 1ms
memory: 4140kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
RDUUULLRRUDDDLLDURDUDRUDLLDDDURRLLUUUDR
result:
wrong answer (1,3) Not Visited