QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#332819 | #7751. Palindrome Path | c20230201 | WA | 1ms | 3860kb | C++14 | 3.1kb | 2024-02-19 16:07:21 | 2024-02-19 16:07:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int sx,sy,ex,ey;
int a[33][33];
int vis[33][33], fa[33][33];
int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
vector<char> ans;
vector<int> g[33][33];
void dfs(int x,int y) {
vis[x][y]=1;
for(int d=0;d<4;d++) {
int tx=x+dx[d], ty=y+dy[d];
if(!a[tx][ty]||vis[tx][ty]) continue;
g[x][y].push_back(d);
fa[tx][ty]=d^1;
dfs(tx,ty);
}
return ;
}
void calc(int x,int y,int d) {
if(d==0) {
int k=0;
while(a[x-k][y]&&a[ex+k][ey]) k++;
if(!a[ex+k][ey]) {
for(int j=1;j<k;j++) ans.push_back('U');
for(int j=1;j<=k;j++) ans.push_back('D');
}else {
for(int j=1;j<=k;j++) ans.push_back('U');
for(int j=1;j<=k;j++) ans.push_back('D');
}
}
if(d==1) {
int k=0;
while(a[x+k][y]&&a[ex-k][ey]) k++;
if(!a[ex-k][ey]) {
for(int j=1;j<k;j++) ans.push_back('D');
for(int j=1;j<=k;j++) ans.push_back('U');
}else {
for(int j=1;j<=k;j++) ans.push_back('D');
for(int j=1;j<=k;j++) ans.push_back('U');
}
}
if(d==2) {
int k=0;
while(a[x][y-k]&&a[ex][ey+k]) k++;
if(!a[ex][ey+k]) {
for(int j=1;j<k;j++) ans.push_back('L');
for(int j=1;j<=k;j++) ans.push_back('R');
}else {
for(int j=1;j<=k;j++) ans.push_back('L');
for(int j=1;j<=k;j++) ans.push_back('R');
}
}
if(d==3) {
int k=0;
while(a[x][y+k]&&a[ex][ey-k]) k++;
if(!a[ex][ey-k]) {
for(int j=1;j<k;j++) ans.push_back('R');
for(int j=1;j<=k;j++) ans.push_back('L');
}else {
for(int j=1;j<=k;j++) ans.push_back('R');
for(int j=1;j<=k;j++) ans.push_back('L');
}
}
return ;
}
void dfs2(int x,int y) {
for(auto d:g[x][y]) {
calc(x,y,d);
dfs2(x+dx[d],y+dy[d]);
calc(x,y,d^1);
}
return ;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n,m; cin>>n>>m;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
char ch; cin>>ch;
a[i][j]=ch-'0';
}
}
cin>>sx>>sy>>ex>>ey;
dfs(sx,sy);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(a[i][j]&&vis[i][j]==0) {
cout<<"-1\n";
exit(0);
}
}
}
dfs2(sx,sy);
vector<int> op;
int fx=ex, fy=ey, tx=sx, ty=sy;
while(fx!=sx||fy!=sy) {
int d=fa[fx][fy];
fx+= dx[d], fy+= dy[d];
op.push_back(d^1);
}
while(op.size()) {
calc(sx,sy,op.back());
int d=op.back(); op.pop_back();
sx+= dx[d], sy+= dy[d];
if(d==0) ans.push_back('D');
if(d==1) ans.push_back('U');
if(d==2) ans.push_back('R');
if(d==3) ans.push_back('L');
}
for(int i=ans.size()-1;i>=0;i--) ans.push_back(ans[i]);
for(auto x:ans) cout<<x;
cout<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3572kb
input:
2 2 11 11 1 1 2 2
output:
DRDUDRLLDUUDDRRRRDDUUDLLRDUDRD
result:
ok Valid Solution (Length = 30).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
UDDLLRRDUDDUUDDDUUUDDDUUUULLRRRUDUDDUDDUDDDDUUDDDUUUDDDUUUUDDDUUUURLLRLLUDUDDRLLUDDUDDDDUUDDDUUUDDDUUUDDDUUUUUDDUDDLLRRDDDUUUUDDDUUUULLRRRUDDUDDUDDUDDRLLDDUUUUDDLLRDDUDDUDDUDDURRRLLUUUUDDDUUUUDDDRRLLDDUDDUUUUUDDDUUUDDDUUUDDDUUDDDDUDDULLRDDUDULLRLLRUUUUDDDUUUUDDDUUUDDDUUDDDDUDDUDDUDURRRLLUUUUDDDUUUDD...
result:
ok Valid Solution (Length = 314).
Test #5:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
RDDDDRLRRLLDUDDUUDDDUUUDDDDUUUURRRLLLRRRRLLLLDDDDRRRRRLLLLLDDUUDDDUUURRRRRLLLLLDDDDUUUUDDDDUUUUURRDDRRRRLLLDDRRDDUUDDDUUUDDDDUUUUDDDDUUUUURRLLRRDDDDDDDDDDDDDDDDRRLLRRUUUUUDDDDUUUUDDDDUUUDDDUUDDRRDDLLLRRRRDDRRUUUUUDDDDUUUUDDDDLLLLLRRRRRUUUDDDUUDDLLLLLRRRRRDDDDLLLLRRRRLLLRRRUUUUDDDDUUUDDDUUDDUDLLRRLRD...
result:
ok Valid Solution (Length = 304).
Test #6:
score: 0
Accepted
time: 0ms
memory: 3572kb
input:
5 3 111 100 111 001 111 4 3 3 2
output:
DRLRLLLRRLRRUURLRLLUULRLRRRLLRLLDDLRRLRRDUURLLLLRUUDRRLRRLDDLLRLLRRRLRLUULLRLRUURRLRRLLLRLRD
result:
ok Valid Solution (Length = 92).
Test #7:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
UDRUDUUDDURUUUUUDDUUDDDUUDDDLULLUUUUDDUUDDDRUUDDLLUUUUUUUULLDDUURDDDUUDDUUUULLULDDDUUDDDUUDDUUUUURUDDUUDURDU
result:
ok Valid Solution (Length = 108).
Test #8:
score: -100
Wrong Answer
time: 1ms
memory: 3584kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
DUUUUDLRLRRUDRLLRLLDDLRLRRRLLRLLUUUULRRRRLUUUULLRLLRRRLRLDDLLRLLRDURRLRLDUUUUD
result:
wrong answer End Point Is (2,1), Not (er = 2, ec = 2)