QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#270092 | #7751. Palindrome Path | time_interspace# | WA | 0ms | 3872kb | C++20 | 2.2kb | 2023-11-30 15:14:32 | 2023-11-30 15:14:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 35, M = 1e6 + 5;
int n, m, sr, sc, er, ec;
int tot, ans[M];
char ch[N][N];
bool used[N][N];
int fx[4] = {-1, 0, 1, 0}, fy[4] = {0, -1, 0, 1};
int dis[N][N][4];
void predfs(int x, int y)
{
used[x][y] = 1;
for (int i = 0; i < 4; i++)
{
int u = x + fx[i], v = y + fy[i];
if (ch[u][v] == '1' && !used[u][v]) predfs(u, v);
}
}
void init()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (ch[i][j] != '1') continue;
for (int k = 0; k < 4; k++)
{
int cur = 0;
while (ch[i + fx[k] * (cur + 1)][j + fy[k] * (cur + 1)] == '1')
{
cur++;
}
dis[i][j][k] = cur;
}
}
}
bool check()
{
predfs(sr, sc);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (ch[i][j] == '1' && !used[i][j]) return 1;
}
return 0;
}
bool isend;
void mv(int x, int y, int i)
{
int j = (i + 2) % 4;
if (dis[x][y][j] < dis[er][ec][i])
{
for (int k = 1; k <= dis[x][y][j]; k++) ans[++tot] = j;
for (int k = 1; k <= dis[x][y][j] + 1; k++) ans[++tot] = i;
}
else
{
for (int k = 1; k <= dis[er][ec][i]; k++) ans[++tot] = j;
for (int k = 1; k <= dis[er][ec][i] + 1; k++) ans[++tot] =i;
}
}
void dfs(int x, int y, int fl)
{
used[x][y] = 1;
if (fl && x == er && y == ec)
{
isend = 1;
return;
}
for (int i = 0; i < 4; i++)
{
int u = x + fx[i], v = y + fy[i];
if (ch[u][v] != '1' || used[u][v]) continue;
mv(x, y, i);
dfs(u, v, fl);
mv(u, v, (i + 2) % 4);
if (isend) return;
}
}
void write(int x)
{
if (x == 0) putchar('U');
if (x == 1) putchar('L');
if (x == 2) putchar('D');
if (x == 3) putchar('R');
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", ch[i] + 1);
scanf("%d%d%d%d", &sr, &sc, &er, &ec);
if (check())
{
puts("-1");
return 0;
}
init();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) used[i][j] = 0;
dfs(sr, sc, 0);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) used[i][j] = 0;
dfs(sr, sc, 1);
for (int i = 1; i <= tot; i++) write(ans[i]);
for (int i = tot; i; i--) write(ans[i]);
puts("");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3808kb
input:
2 2 11 11 1 1 2 2
output:
DRUDLUDRLUULRDULDURD
result:
ok Valid Solution (Length = 20).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3868kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
DUUDDUUUDDDUUUURLLDUDDUDDUDDRLRRUDUUDDUUUDDDUUUULLRRRDUDDUDDUDDUDUUDDUUUDDDUUUULDUDDUDDUDDRLLRLLUDUUDDUUUDDDUUUURDUDDUDDDDUDDUDRUUUUDDDUUUDDUUDULLRLLRDDUDDUDDUDLUUUUDDDUUUDDUUDUDDUDDUDDUDRRRLLUUUUDDDUUUDDUUDURRLRDDUDDUDDUDLLRUUUUDDDUUUDDUUD
result:
wrong answer End Point Is (2,3), Not (er = 4, ec = 2)