QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#394449 | #7751. Palindrome Path | tanxi | RE | 0ms | 0kb | C++14 | 3.5kb | 2024-04-20 14:51:30 | 2024-04-20 14:51:31 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+9;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
char ch[4]={'R','L','D','U'};
int f[39][39][4];
int a[39][39],vis[39][39];
pair<int,int>stk[N];
int top,n,m;
void dfs(int x,int y)
{
vis[x][y]=1;
stk[++top]={x,y};
for(int t=0;t<4;t++)
{
int nx=x+dx[t];
int ny=y+dy[t];
if(!a[nx][ny])
continue;
if(vis[nx][ny])
continue;
dfs(nx,ny);
stk[++top]={x,y};
}
}
int stx,sty,edx,edy;
string s;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("er.err","w",stderr);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
char c;
cin>>c;
a[i][j]=c-'0';
}
}
cin>>stx>>sty>>edx>>edy;
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(!a[i][j])
{
f[i][j][3]=f[i][j][1]=-1;
}
else
{
f[i][j][3]=f[i-1][j][3]+1;
f[i][j][1]=f[i][j-1][1]+1;
}
}
}
for(int i=n;i>=1;i--)
{
for(int j=n;j>=1;j--)
{
if(!a[i][j])
{
f[i][j][2]=f[i][j][0]=-1;
}
else
{
f[i][j][2]=f[i+1][j][2]+1;
f[i][j][0]=f[i][j+1][0]+1;
}
}
}
dfs(stx,sty);
if(!vis[edx][edy])
{
cout<<-1;
return 0;
}
for(int i=1;i<=top;i++)
{
stk[++top]=stk[i];
if(stk[i].first==edx&&stk[i].second==edy)
break;
}
for(int i=1;i<top;i++)
{
int x=stk[i].first,y=stk[i].second;
for(int t=0;t<4;t++)
{
if(stk[i+1].first==x+dx[t]&&stk[i+1].second==y+dy[t])
{
// cerr<<x<<','<<y<<"to"<<stk[i+1].first<<','<<stk[i+1].second<<'\n';
int k=f[x][y][t^1];
int p=f[edx][edy][t];
if(k==p)
{
for(int j=1;j<=k;j++)
{
s+=ch[t^1];
// cerr<<ch[t^1];
}
for(int j=1;j<=k+1;j++)
{
s+=ch[t];
// cerr<<ch[t];
}
}
else
if(k>p)
{
for(int j=1;j<=p;j++)
{
s+=ch[t^1];
// cerr<<ch[t^1];
}
for(int j=1;j<=p+1;j++)
{
s+=ch[t];
// cerr<<ch[t];
}
}
else
{
for(int j=1;j<=k+1;j++)
{
s+=ch[t^1];
// cerr<<ch[t^1];
}
for(int j=1;j<=k+1;j++)
{
s+=ch[t];
// cerr<<ch[t];
}
}
// cerr<<'\n';
break;
}
}
}
cout<<s;
reverse(s.begin(),s.end());
cout<<s;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Dangerous Syscalls
input:
2 2 11 11 1 1 2 2