QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#403657 | #7751. Palindrome Path | ucup-team3160# | WA | 1ms | 3620kb | C++14 | 3.4kb | 2024-05-02 16:47:14 | 2024-05-02 16:47:16 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf=1e18+5;
const ll mod=998244353;
const double eps=1e-15;
inline ll read()
{
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline char getc()
{
char ch=getchar();
while(ch!='0'&&ch!='1'){ch=getchar();}
return ch;
}
ll a[35][35];
char c[2000005],d[2000005];ll cntc,cntd;
ll vis[35][35][35][35];
ll flag[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
char fla[4]={'D','U','R','L'};
bool ok;
void dfs(ll &sx,ll &sy,ll &tx,ll &ty,ll tox,ll toy)
{
if(sx==tox&&sy==toy)
{
ok=1;return;
}
if(vis[sx][sy][tx][ty])return;
vis[sx][sy][tx][ty]=1;
ll fsx=sx,fsy=sy,ftx=tx,fty=ty;
for(int i=0;i<4;i++)
{
if(a[tx+flag[i][0]][ty+flag[i][1]]
&& !a[tx-flag[i][0]][ty-flag[i][1]])continue;
if(!a[tx+flag[i][0]][ty+flag[i][1]])
{
if(a[sx+flag[i][0]][sy+flag[i][1]])sx+=flag[i][0],sy+=flag[i][1];
c[++cntc]=fla[i];
dfs(sx,sy,tx,ty,tox,toy);
if(ok)return;
cntc--;
sx=fsx,sy=fsy,tx=ftx,ty=fty;
}
if(a[tx-flag[i][0]][ty-flag[i][1]])
{
tx-=flag[i][0],ty-=flag[i][1];
if(a[sx+flag[i][0]][sy+flag[i][1]])sx+=flag[i][0],sy+=flag[i][1];
c[++cntc]=fla[i];
dfs(sx,sy,tx,ty,tox,toy);
if(ok)return;
cntc--;
sx=fsx,sy=fsy,tx=ftx,ty=fty;
}
}
}
ll visx[35][35];
void dfsx(ll x,ll y)
{
if(visx[x][y])return;
visx[x][y]=1;
for(int i=0;i<4;i++)
{
ll nx=x+flag[i][0],ny=y+flag[i][1];
if(a[nx][ny]&&!visx[nx][ny])
{
d[++cntd]=fla[i];
dfsx(nx,ny);
}
}
}
void solve()
{
ll n=read(),m=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
a[i][j]=getc()-'0';
}
}
ll sx=read(),sy=read(),tx=read(),ty=read();
while(sx!=tx||sy!=ty)
{
ok=0;
dfs(sx,sy,tx,ty,tx,ty);
if(!ok){cout<<-1<<'\n';return;}
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
{
for(int p=1;p<=n;p++)for(int q=1;q<=m;q++)
{
vis[i][j][p][q]=0;
}
}
}
dfsx(sx,sy);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]&&(!visx[i][j])){cout<<-1<<'\n';return;}
}
}
for(int i=1;i<=cntc;i++)cout<<c[i];
for(int i=1;i<=cntd;i++)cout<<d[i];
for(int i=1;i<=cntd;i++)
{
if(d[i]=='L')cout<<'R';
if(d[i]=='R')cout<<'L';
if(d[i]=='U')cout<<'D';
if(d[i]=='D')cout<<'U';
}
for(int i=cntd;i>=1;i--)
{
if(d[i]=='L')cout<<'R';
if(d[i]=='R')cout<<'L';
if(d[i]=='U')cout<<'D';
if(d[i]=='D')cout<<'U';
}
for(int i=cntd;i>=1;i--)cout<<d[i];
for(int i=cntc;i>=1;i--)cout<<c[i];
if(!cntc&&!cntd)cout<<'\n';
return;
}
int main()
{
// clock_t start=clock();
ll t=1;
while(t--)solve();
// clock_t end=clock();
// cout<<(end-start)*1.00/CLOCKS_PER_SEC<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3548kb
input:
2 2 11 11 1 1 2 2
output:
DDURUDULDDRUURDDLUDURUDD
result:
ok Valid Solution (Length = 24).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3556kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
DRUUUURDDDDLDDLDDUUULDDDDLUUUURUURUUDDDDUURUURUUUULDDDDLUUUDDLDDLDDDDRUUUURD
result:
wrong answer End Point Is (2,3), Not (er = 4, ec = 2)