QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#403692 | #7751. Palindrome Path | ucup-team3160# | WA | 1ms | 5684kb | C++14 | 3.3kb | 2024-05-02 17:27:38 | 2024-05-02 17:27:39 |
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)
{
if(sx==tx&&sy==ty)
{
ok=1;return;
}
for(int i=0;i<4;i++)
{
if(sx+flag[i][0]==tx&&sy+flag[i][1]==ty)
{
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);
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);
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();
dfsx(sx,sy);
dfs(sx,sy,tx,ty);
if(!ok){cout<<-1<<'\n';return;}
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<=cntd;i++)cout<<d[i];
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=1;i<=cntc;i++)cout<<c[i];
for(int i=cntc;i>=1;i--)cout<<c[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--)cout<<d[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: 5684kb
input:
2 2 11 11 1 1 2 2
output:
DRUDLUDDULDURD
result:
ok Valid Solution (Length = 14).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3552kb
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2
output:
DRUUUURDDDDLDDLDDUUDDUURUURUUUULDDDDLUULDDDDLUUUURUURUUDDUUDDLDDLDDDDRUUUURD
result:
wrong answer End Point Is (2,3), Not (er = 4, ec = 2)