QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394571 | #7751. Palindrome Path | lfxxx | WA | 1ms | 4072kb | C++17 | 4.0kb | 2024-04-20 16:18:58 | 2024-04-20 16:18:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 35;
int n, m, x, y, xx, yy;
char pre[N][N];
char a[N][N];
bool vis[N][N];
string s, ans;
#define ck(x, y) (1 <= x && x <= n && 1 <= y && y <= m && !vis[x][y])
void dfs(int x, int y)
{
vis[x][y] = 1;
if (ck(x + 1, y)) {
ans += "U";
dfs(x + 1, y);
ans += "D";
}
if (ck(x - 1, y)) {
ans += "D";
dfs(x - 1, y);
ans += "U";
}
if (ck(x, y + 1)) {
vis[x][y + 1] = 1;
ans += "L";
dfs(x, y + 1);
ans += "R";
}
if (ck(x, y - 1)) {
vis[x][y - 1] = 1;
ans += "R";
dfs(x, y - 1);
ans += "L";
}
}
void D()
{
int d = 0;
while (a[x - d - 1][y] == '1' && a[xx + d + 1][yy] == '1') ++d;
if (a[xx + d + 1][yy] == '1') {
for (int i = 0; i <= d; ++i) ans += 'U';
for (int i = 0; i <= d; ++i) ans += 'D';
} else {
for (int i = 1; i <= d; ++i) ans += 'U';
for (int i = 0; i <= d; ++i) ans += 'D';
}
++x;
}
void U()
{
int d = 0;
while (a[x + d + 1][y] == '1' && a[xx - d - 1][yy] == '1') ++d;
if (a[xx - d - 1][yy] == '1') {
for (int i = 0; i <= d; ++i) ans += 'D';
for (int i = 0; i <= d; ++i) ans += 'U';
} else {
for (int i = 1; i <= d; ++i) ans += 'D';
for (int i = 0; i <= d; ++i) ans += 'U';
}
--x;
}
void R()
{ int d = 0;
while (a[x][y - d - 1] == '1' && a[xx][yy + d + 1] == '1') ++d;
if (a[xx][yy + d + 1] == '1') {
for (int i = 0; i <= d; ++i) ans += 'L';
for (int i = 0; i <= d; ++i) ans += 'R';
} else {
for (int i = 1; i <= d; ++i) ans += 'L';
for (int i = 0; i <= d; ++i) ans += 'R';
}
++y;
}
void L()
{
int d = 0;
while (a[x][y + d + 1] == '1' && a[xx][yy - d - 1] == '1') ++d;
if (a[xx][yy - d - 1] == '1') {
for (int i = 0; i <= d; ++i) ans += 'R';
for (int i = 0; i <= d; ++i) ans += 'L';
} else {
for (int i = 1; i <= d; ++i) ans += 'R';
for (int i = 0; i <= d; ++i) ans += 'L';
}
--y;
}
void bfs()
{
queue<pii>q;
q.emplace(x, y);
vis[x][y] = 1;
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
if (ck(x + 1, y)) {
vis[x + 1][y] = 1;
pre[x + 1][y] = 'D';
q.emplace(x + 1, y);
}
if (ck(x - 1, y)) {
vis[x - 1][y] = 1;
pre[x - 1][y] = 'U';
q.emplace(x - 1, y);
}
if (ck(x, y + 1)) {
vis[x][y + 1] = 1;
pre[x][y + 1] = 'R';
q.emplace(x, y + 1);
}
if (ck(x, y - 1)) {
vis[x][y - 1] = 1;
pre[x][y - 1] = 'L';
q.emplace(x, y - 1);
}
}
}
bool en;
int main() {
cerr << (&be - &en) / 1024.0 / 1024 << " MB\n--------------------------------" << endl;
#ifdef IAKIOI
freopen("in.in", "r", stdin);
// freopen("out.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
cin >> a[i][j];
if (a[i][j] == '0') vis[i][j] = 1;
}
}
cin >> x >> y >> xx >> yy;
dfs(xx, yy);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] == '1' && !vis[i][j]) {
cout << "-1\n";
return 0;
}
}
}
for (char c : ans) {
if (c == 'U') {
if (a[x - 1][y] == '1') --x;
} else if (c == 'D') {
if (a[x + 1][y] == '1') ++x;
} else if (c == 'R') {
if (a[x][y + 1] == '1') ++y;
} else {
if (a[x][y - 1] == '1') --y;
}
}
// ans = "";
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] == '0') vis[i][j] = 1;
}
}
bfs();
int X = xx, Y = yy;
while (xx != x || yy != y) {
s += pre[xx][yy];
if (pre[xx][yy] == 'D') --xx;
else if (pre[xx][yy] == 'U') ++xx;
else if (pre[xx][yy] == 'R') --yy;
else ++yy;
}
xx = X, yy = Y;
reverse(all(s));
// cerr << s << endl;
for (char c : s) {
if (c == 'D') D(), ++x;
else if (c == 'U') U(), --x;
else if (c == 'R') R(), ++y;
else L(), --y;
}
cout << ans;
reverse(all(ans));
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3928kb
input:
2 2 11 11 1 1 2 2
output:
DRUDLUDRRDULDURD
result:
ok Valid Solution (Length = 16).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 1ms
memory: 3772kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 3824kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
ULDDDDLUUUUDDDDRRUURUUDDDDUULDDLUUUURDUDDUDDRLLRDDUDDUDRUUUULDDLUUDDDDUURUURRDDDDUUUULDDDDLU
result:
ok Valid Solution (Length = 92).
Test #5:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
DDDDRRUUUULRRRDDDDLRUULRUULLDDLRDDLLUUUUDDDDRRRRRRRRDDDDUUUULLDDRLDDLLUURLUURLDDDDRRRLUUUURRDDDD
result:
ok Valid Solution (Length = 96).
Test #6:
score: 0
Accepted
time: 0ms
memory: 4072kb
input:
5 3 111 100 111 001 111 4 3 3 2
output:
LUURRLLDDRRDDLLRRUULLUURRLLDDRRDDLLRRUUL
result:
ok Valid Solution (Length = 40).
Test #7:
score: 0
Accepted
time: 0ms
memory: 3848kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
UULDULUUDLDDDUUURDRRDDULUULUDDRRDRUUUDDDLDUULUDLUU
result:
ok Valid Solution (Length = 50).
Test #8:
score: 0
Accepted
time: 1ms
memory: 3832kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
LDURRUUUDLLRRDDDULRLLUULRRLUULLRLUDDDRRLLDUUURRUDL
result:
ok Valid Solution (Length = 50).
Test #9:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
5 5 01110 10110 11110 11011 11100 2 4 5 1
output:
DDDULUULRDDLDDLUUULRDDDRRLUURRUUDDLLDDLLDDLLDDUURRUULRRDDDRLUUULDDLDDRLUULUDDD
result:
ok Valid Solution (Length = 78).
Test #10:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
5 3 011 111 110 111 011 3 1 2 1
output:
UULULDURDDDDLUDRUUURDDULUULLUULUDDRUUURDULDDDDRUDLULUU
result:
ok Valid Solution (Length = 54).
Test #11:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
4 5 11111 11111 11111 11111 3 2 1 3
output:
UUULDDDLUUUDDDRUUURRDDDRUUUDDDLUUULDDDUUUUUUDDDLUUULDDDUUURDDDRRUUURDDDUUULDDDLUUU
result:
ok Valid Solution (Length = 82).
Test #12:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
5 5 11111 10101 11111 10101 11111 2 5 1 1
output:
UUUULLDDDDLLUUUURLDDRLDDRRRLUURLUURRDDDDUUUULLLLLLLLUUUUDDDDRRUULRUULRRRDDLRDDLRUUUULLDDDDLLUUUU
result:
ok Valid Solution (Length = 96).
Test #13:
score: 0
Accepted
time: 0ms
memory: 3760kb
input:
4 5 11111 10000 11111 00001 1 3 4 5
output:
DRRRRDDLLLLRRRRUULLLLUDDRRRRDDRRRRDDULLLLUURRRRLLLLDDRRRRD
result:
ok Valid Solution (Length = 58).
Test #14:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
3 5 10100 00010 00111 1 3 1 1
output:
-1
result:
ok No Solution.
Test #15:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
4 5 10001 11111 11100 11111 4 5 3 1
output:
ULDDLUULLRRDDLLDURRRRDULUURDLLLLDRUULUDRRRRUDLLDDRRLLUULDDLU
result:
ok Valid Solution (Length = 60).
Test #16:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
3 5 11111 10100 11111 1 2 3 5
output:
RRDDLLRRRRUULRDDLLUULLDDRRRRRRRRDDLLUULLDDRLUURRRRLLDDRR
result:
ok Valid Solution (Length = 56).
Test #17:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
4 5 01110 10101 11011 10111 1 3 2 3
output:
-1
result:
ok No Solution.
Test #18:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
5 5 11111 11111 11111 11111 11111 1 3 5 2
output:
DDDDLUUUULDDDDLUUUUDDDDRUUUURDDDDRRUUUUDDDDLUUUUDDDDRLRLLRLRDDDDUUUULDDDDUUUURRDDDDRUUUURDDDDUUUULDDDDLUUUULDDDD
result:
ok Valid Solution (Length = 112).
Test #19:
score: 0
Accepted
time: 0ms
memory: 3888kb
input:
5 5 11111 10101 11111 10101 11111 5 1 2 3
output:
UUULLDDDDRRRRUUUULRDDLRDDLLLLUURLUURRDDDDUUDUUUUDUUDDDDRRUULRUULLLLDDRLDDRLUUUURRRRDDDDLLUUU
result:
ok Valid Solution (Length = 92).
Test #20:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
5 5 11111 10000 11111 00001 11111 4 5 5 3
output:
LLDDRRRRDDLLLLRRRRUULLLLUURRRRLLRRLLLRRLLLDDLRLRLLRRRLLRRRDDRLRLLRLRDDRRRLLRRRLLRLRLDDLLLRRLLLRRLLRRRRUULLLLUURRRRLLLLDDRRRRDDLL
result:
ok Valid Solution (Length = 128).
Test #21:
score: 0
Accepted
time: 0ms
memory: 3964kb
input:
5 5 01010 10101 10101 11001 10011 4 1 5 4
output:
-1
result:
ok No Solution.
Test #22:
score: -100
Wrong Answer
time: 0ms
memory: 3828kb
input:
5 5 10101 11111 10101 11111 11111 3 1 2 4
output:
LUUURDRURDRUDDDDULLUDDURRUULULDLULDDDDURLRRUULRRLUURRLRUDDDDLULDLULUURRUDDULLUDDDDURDRURDRUUUL
result:
wrong answer (1,5) Not Visited