QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394398 | #7751. Palindrome Path | OccDreamer | WA | 1ms | 3828kb | C++14 | 3.9kb | 2024-04-20 14:18:52 | 2024-04-20 14:18:52 |
Judging History
answer
//OccDreamer
#include<bits/stdc++.h>
#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << " -_- " << endl
#define debug cerr << " ------------------- " << endl
#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)
#define NO puts("No")
#define YES puts("Yes")
//#define OccDreamer
//#define int long long
using namespace std;
namespace IO{
inline int read(){
int X=0, W=0; char ch=getchar();
while(!isdigit(ch)) W|=ch=='-', ch=getchar();
while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
return W?-X:X;
}
inline void write(int x){
if(x<0) x=-x, putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
inline void sprint(int x){write(x), putchar(32);}
inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;
const int MAXN = 35;
const int mod = 998244353;
const int rx[]={1,-1,0,0}, ry[]={0,0,1,-1};
const char dir[]={'D','U','R','L'};
int ax, ay, bx, by;
int n, m, tot, all[4];
char s[MAXN][MAXN];
bool vis[MAXN][MAXN];
vc<char> ans;
inline void dfs(int x, int y){
vis[x][y]=1; --tot;
for(int i=0;i<4;++i){
int tx=x+rx[i], ty=y+ry[i];
if(tx>=1 && ty>=1 && tx<=n && ty<=m && s[tx][ty]=='1' && !vis[tx][ty]) dfs(tx,ty);
}
return ;
}
inline void construct(int x, int y){
vis[x][y]=1;
for(int i=0;i<4;++i){
int tx=x+rx[i], ty=y+ry[i];
if(tx>=1 && ty>=1 && tx<=n && ty<=m && s[tx][ty]=='1' && !vis[tx][ty]){
int sum=0, A=x, B=y;
while(s[A][B]=='1' && A>=1 && B>=1 && A<=n && B<=m) A+=rx[i^1], B+=ry[i^1], sum++;
if(sum<all[i]){
for(int j=1;j<=sum;++j) ans.pb(dir[i^1]);
for(int j=1;j<=sum;++j) ans.pb(dir[i]);
}
else{
for(int j=1;j<all[i];++j) ans.pb(dir[i^1]);
for(int j=1;j<=all[i];++j) ans.pb(dir[i]);
}
construct(tx,ty);
A=tx, B=ty;
while(s[A][B]=='1' && A>=1 && B>=1 && A<=n && B<=m) A+=rx[i^1], B+=ry[i], sum++;
if(sum<all[i^1]){
for(int j=1;j<=sum;++j) ans.pb(dir[i]);
for(int j=1;j<=sum;++j) ans.pb(dir[i^1]);
}
else{
for(int j=1;j<all[i^1];++j) ans.pb(dir[i]);
for(int j=1;j<=all[i^1];++j) ans.pb(dir[i^1]);
}
}
}
return ;
}
inline void construct2(int x, int y){
if(x==bx && y==by){
for(auto i:ans) putchar(i);
reverse(ans.begin(),ans.end());
for(auto i:ans) putchar(i);
exit(0);
}
vis[x][y]=1;
for(int i=0;i<4;++i){
int tx=x+rx[i], ty=y+ry[i];
if(tx>=1 && ty>=1 && tx<=n && ty<=m && s[tx][ty]=='1' && !vis[tx][ty]){
int sum=0, A=x, B=y;
while(s[A][B]=='1' && A>=1 && B>=1 && A<=n && B<=m) A+=rx[i^1], B+=ry[i^1], sum++;
if(sum<all[i]){
for(int j=1;j<=sum;++j) ans.pb(dir[i^1]);
for(int j=1;j<=sum;++j) ans.pb(dir[i]);
}
else{
for(int j=1;j<all[i];++j) ans.pb(dir[i^1]);
for(int j=1;j<=all[i];++j) ans.pb(dir[i]);
}
construct2(tx,ty);
A=tx, B=ty;
while(s[A][B]=='1' && A>=1 && B>=1 && A<=n && B<=m) A+=rx[i^1], B+=ry[i], sum++;
if(sum<all[i^1]){
for(int j=1;j<=sum;++j) ans.pb(dir[i]);
for(int j=1;j<=sum;++j) ans.pb(dir[i^1]);
}
else{
for(int j=1;j<all[i^1];++j) ans.pb(dir[i]);
for(int j=1;j<=all[i^1];++j) ans.pb(dir[i^1]);
}
}
}
return ;
}
signed main(){
n=read(), m=read();
for(int i=1;i<=n;++i){
scanf("%s",s[i]+1);
for(int j=1;j<=m;++j) tot+=s[i][j]=='1';
}
ax=read(), ay=read(), bx=read(), by=read();
if(s[ax][ay]=='0' || s[bx][by]=='0') return eprint(-1), 0;
dfs(ax,ay); if(tot) return eprint(-1), 0; memset(vis,0,sizeof vis);
for(int i=0;i<4;++i){
all[i]=0; int A=bx, B=by;
while(s[A][B]=='1' && A>=1 && B>=1 && A<=n && B<=m) A=A+rx[i], B=B+ry[i], all[i]++;
}
construct(ax,ay); memset(vis,0,sizeof vis); construct2(ax,ay);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3768kb
input:
2 2 11 11 1 1 2 2
output:
DRDUDRLLDUUDRRDUUDLLRDUDRD
result:
ok Valid Solution (Length = 26).
Test #2:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
UDDLLRRDUDDUUDDDUUUDDDUUUULLRRRUDUDDUDDUDDDDDUUUUDDDUUUUDDDUUUUDDDUUURLLRLLUDUDDRLLUDDUDDDDDUUUUDDDUUUUDDDUUUDDDUUUUUDDUDDLLRRRDDDUUUUDDDUUULLRRRUDDUDDUDDUDDRLLDDDUUUUUUUUDDDLLRDDUDDUDDUDDURRRLLUUUDDDUUUUDDDRRRLLDDUDDUUUUUDDDUUUDDDUUUUDDDUUUUDDDDDUDDULLRDDUDULLRLLRUUUDDDUUUUDDDUUUUDDDUUUUDDDDDUDDUDD...
result:
ok Valid Solution (Length = 334).
Test #5:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
5 5 11111 10101 11111 10101 11111 1 4 5 5
output:
RDDDDRLRRLLDUDDUUDDDUUUDDDDUUUURRRLLLRRRRLLLLDDDDRRRRRLLLLLDDDDUUUUUDDDDUUUUURRRRRLLLLLDDDDUUUUUDDDUUURRDDRRRRRLLLLLDDRRDDDDUUUUUDDDDUUUUUDDDDUUUUUDDDUUURRRRLLLLLRDDDDDDDDRLLLLLRRRRUUUDDDUUUUUDDDDUUUUUDDDDUUUUUDDDDRRDDLLLLLRRRRRDDRRUUUDDDUUUUUDDDDLLLLLRRRRRUUUUUDDDDUUUUUDDDDLLLLLRRRRRDDDDLLLLRRRRLLL...
result:
ok Valid Solution (Length = 334).
Test #6:
score: 0
Accepted
time: 1ms
memory: 3688kb
input:
5 3 111 100 111 001 111 4 3 3 2
output:
DRLRLLLRRLRRUURLRLLUULRLRRRLLRLLDDLRRLRRDDRLRLLLRRLRRUURLLRUURRLRRLLLRLRDDRRLRRLDDLLRLLRRRLRLUULLRLRUURRLRRLLLRLRD
result:
ok Valid Solution (Length = 114).
Test #7:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
5 4 1001 1101 1111 0011 0010 2 2 1 1
output:
UDRUDUUDDURUUUUUDDDUUDDDUUDDDLULLUUUUDDDUUDDDRUUDRUDUUDDURUUUUUDDDUUDDDUUDDDLULLUUUULLULDDDUUDDDUUDDDUUUUURUDDUUDURDUURDDDUUDDDUUUULLULDDDUUDDDUUDDDUUUUURUDDUUDURDU
result:
ok Valid Solution (Length = 164).
Test #8:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
5 3 101 111 100 111 100 4 1 2 2
output:
DUUUUDLRLRRUDRLLRLLDDLRLRRRLLRLLDUUUUDLRRLDUUUUDLLRLLRRRLRLDDLLRLLRDURRLRLDUUUUD
result:
ok Valid Solution (Length = 80).
Test #9:
score: -100
Wrong Answer
time: 0ms
memory: 3728kb
input:
5 5 01110 10110 11110 11011 11100 2 4 5 1
output:
DDLRLDDDUUUULDUDDUULLRRLLLLRRRDDLDDLLRRLLDUDDUUDDDUUUDDDLLRRRDDDUUUUDDDUUULLRRRLLRRRDDDUUUUDDLRLDDDUUUULDUDDUULLRRLLLLRRRDDLDDLLRRLLLLRRLLDDLDDRRRLLLLRRLLUUDDUDLUUUUDDDLRLDDUUUUDDDRRRLLRRRLLUUUDDDUUUUDDDRRRLLDDDUUUDDDUUDDUDLLRRLLDDLDDRRRLLLLRRLLUUDDUDLUUUUDDDLRLDD
result:
wrong answer End Point Is (4,4), Not (er = 5, ec = 1)