QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#638964 | #7751. Palindrome Path | zzuqy# | TL | 0ms | 3824kb | C++14 | 2.9kb | 2024-10-13 17:26:17 | 2024-10-13 17:26:22 |
Judging History
answer
#include<bits/stdc++.h>
#define N 39
using namespace std;
bool vst[N][N];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
char dir[4]={'U','D','L','R'};
char c[N][N];
string ans,ans2,mid;
int n,m;
bool ok(int x,int y){
//cout<<x<<" "<<y<<endl;
if(x<1||x>n||y<1||y>m)return 0;
//cout<<"fuck"<<endl;
if(c[x][y]=='0')return 0;
return 1;
}
void dfs(int x,int y){
vst[x][y]=1;
for(int k=0;k<4;k++){
int nx=x+dx[k],ny=y+dy[k];
if(!ok(nx,ny))continue;
if(vst[nx][ny])continue;
ans+=dir[k];
dfs(nx,ny);
ans+=dir[k^1];
}
}
void move(int &x,int &y,int dir){
int nx=x+dx[dir],ny=y+dy[dir];
//cout<<nx<<" "<<ny<<endl;
if(ok(nx,ny))x=nx,y=ny;
//cout<<x<<" "<<y<<endl;
}
void move(int &x,int &y,char dir){
if(dir=='U')move(x,y,0);
if(dir=='D')move(x,y,1);
if(dir=='L')move(x,y,2);
if(dir=='R')move(x,y,3);
}
int sx,sy,tx,ty;
struct node{
int x1,y1,x2,y2;
bool operator ==(const node&a){
return x1==a.x1&&y1==a.y1&&x2==a.x2&&y2==a.y2;
}
bool operator !=(const node&a){
return x1!=a.x1||y1!=a.y1||x2!=a.x2||y2!=a.y2;
}
};
node f[N][N][N][N];
int g[N][N][N][N];
int main(){
//freopen("1.in","r",stdin);
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>c[i][j];
}
cin>>sx>>sy>>tx>>ty;
dfs(tx,ty);
reverse(ans.begin(),ans.end());
for(auto i:ans)move(sx,sy,i);
//cout<<sx<<" "<<sy<<" "<<tx<<" "<<ty<<endl;
//cout<<ans<<endl;
queue<node>q;
q.push((node){sx,sy,tx,ty});
while(!q.empty()){
auto now=q.front();q.pop();
int x=now.x1,y=now.y1,lx=now.x2,ly=now.y2;
//cout<<x<<" "<<y<<" "<<lx<<" "<<ly<<endl;
for(int k=0;k<4;k++){
int nx=now.x1,ny=now.y1;
move(nx,ny,k);
if(!ok(lx+dx[k],ly+dy[k])){
if(f[nx][ny][lx][ly]==(node){0,0,0,0}){
f[nx][ny][lx][ly]=(node){x,y,lx,ly};
g[nx][ny][lx][ly]=k;
q.push((node){nx,ny,lx,ly});
}
}
if(ok(lx-dx[k],ly-dy[k])){
if(f[nx][ny][lx-dx[k]][ly-dy[k]]==(node){0,0,0,0}){
f[nx][ny][lx-dx[k]][ly-dy[k]]=(node){x,y,lx,ly};
g[nx][ny][lx-dx[k]][ly-dy[k]]=k;
q.push((node){nx,ny,lx-dx[k],ly-dy[k]});
}
}
}
}
//cout<<"OK";
//cout<<sx<<" "<<sy<<" "<<tx<<" "<<ty<<endl;
int x1=0,x2=0,y1=0,y2=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(ok(i,j)&&f[i][j][i][j]!=(node){0,0,0,0}){
x1=i,y1=j,x2=i,y2=j;mid="";
}
for(int k=0;k<4;k++){
if(ok(i,j)&&ok(i+dx[k],j+dy[k])&&f[i][j][i+dx[k]][j+dy[k]]!=(node){0,0,0,0}){
x1=i,y1=j,x2=i+dx[k],y2=j+dy[k];
mid=dir[k];
}
}
}
//cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
if(x1==0){
cout<<-1;
return 0;
}
//cout<<"OK";
while(!(x1==sx&&y1==sy&&x2==tx&&y2==ty)){
ans2+=dir[g[x1][y1][x2][y2]];
auto tmp=f[x1][y1][x2][y2];
//cout<<x1<<" "<<y1<<" "<<x2<<" "<<y2<<endl;
x1=tmp.x1;y1=tmp.y1;x2=tmp.x2;y2=tmp.y2;
}
reverse(ans2.begin(),ans2.end());
ans+=ans2;
ans2=ans;
reverse(ans2.begin(),ans2.end());
ans+=mid+ans2;
cout<<ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3824kb
input:
2 2 11 11 1 1 2 2
output:
DRUDLUDRLRDULDURD
result:
ok Valid Solution (Length = 17).
Test #2:
score: 0
Accepted
time: 0ms
memory: 3508kb
input:
2 2 10 01 1 1 2 2
output:
-1
result:
ok No Solution.
Test #3:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
1 1 1 1 1 1 1
output:
result:
ok Valid Solution (Length = 0).
Test #4:
score: -100
Time Limit Exceeded
input:
5 4 1111 1111 1111 1111 1111 4 2 4 2