QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394546 | #7751. Palindrome Path | lfxxx | WA | 0ms | 4100kb | C++17 | 3.9kb | 2024-04-20 15:59:35 | 2024-04-20 15:59:36 |
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';
}
}
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';
}
}
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';
}
}
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';
}
}
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;
}
}
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();
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;
}
reverse(all(s));
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: 0ms
memory: 4032kb
input:
2 2 11 11 1 1 2 2
output:
DRUDLUDLRRLDULDURD
result:
ok Valid Solution (Length = 18).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3864kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3904kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
ULDDDDLUUUUDDDDRRUURUUDDDDUULDDLUUUURDUDDUDDRRLLLLRRDDUDDUDRUUUULDDLUUDDDDUURUURRDDDDUUUULDDDDLU
result:
ok Valid Solution (Length = 96).
Test #5:
score: 0
Accepted
time: 0ms
memory: 4100kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
DDDDRRUUUULRRRDDDDLRUULRUULLDDLRDDLLUUUUDDDDLRLLRRLLLRRRLLLLRRRRRRRRLLLLRRRLLLRRLLRLDDDDUUUULLDDRLDDLLUURLUURLDDDDRRRLUUUURRDDDD
result:
ok Valid Solution (Length = 128).
Test #6:
score: 0
Accepted
time: 0ms
memory: 3916kb
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: 3864kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
UULDULUUDLDDDUUURDRRDDURLUULRUDDRRDRUUUDDDLDUULUDLUU
result:
ok Valid Solution (Length = 52).
Test #8:
score: 0
Accepted
time: 0ms
memory: 3880kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
LDURRUUUDLLRRDDDULRLLUULRRLUULLRLUDDDRRLLDUUURRUDL
result:
ok Valid Solution (Length = 50).
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3868kb
input:
5 5 01110 10110 11110 11011 11100 2 4 5 1
output:
DDDULUULRDDLDDLUUULRDDDRRLUURRUUDDRLRRLLDDRRLLLLRRDDLLRRLRDDUURRUULRRDDDRLUUULDDLDDRLUULUDDD
result:
wrong answer (4,5) Not Visited