QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#80597 | #3816. Home alone: Johnny lost in New York | fansizhe | RE | 2ms | 7688kb | C++23 | 9.0kb | 2023-02-24 13:24:15 | 2023-02-24 13:24:18 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
char ch[]={'L','D','P','G'};
int to[1005][1005],ans,vis[1005][1005];
void dfs(int x,int y,int n,int m,int sx,int sy,int tx,int ty,int px,int py){
if(y>m)y=1,x++;
if(x>n){
int x=sx,y=sy,cnt=1;
while(x!=tx||y!=ty){
int k=to[x+px][y+py];
x+=dx[k],y+=dy[k];
cnt++;
}
if(cnt!=n*m)return;
ans=1;
return;
}
if(x==tx&&y==ty)dfs(x,y+1,n,m,sx,sy,tx,ty,px,py);
else for(int k=0;k<4;k++){
int xx=x+dx[k],yy=y+dy[k];
if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&!vis[xx][yy]){
if((k==0||k==3)&&to[xx+px][yy+py]==(k^2))continue;
to[x+px][y+py]=k;
vis[xx][yy]=1;
dfs(x,y+1,n,m,sx,sy,tx,ty,px,py);
vis[xx][yy]=0;
if(ans==1)return;
}
}
}
void solve(int n,int m,int sx,int sy,int tx,int ty,int px,int py){
// printf("%d,%d,%d,%d,%d,%d,%d,%d\n",n,m,sx,sy,tx,ty,px,py);
if(n<=5&&m<=5)vis[sx][sy]=1,dfs(1,1,n,m,sx,sy,tx,ty,px,py),vis[sx][sy]=0;
else if(n>5&&sx>2&&tx>2){
solve(n-2,m,sx-2,sy,tx-2,ty,px+2,py);
for(int i=1;i<=m;i++)
if(to[px+3][py+i]==1){
to[px+3][py+i]=0;
for(int j=i;j>1;j--)to[px+2][py+j]=3;
to[px+2][py+1]=0;
for(int j=1;j<m;j++)to[px+1][py+j]=1;
to[px+1][py+m]=2;
for(int j=m;j>i+1;j--)to[px+2][py+j]=3;
to[px+2][py+i+1]=2;
break;
}else if(to[px+3][py+i]==3){
to[px+3][py+i]=0;
for(int j=i;j<m;j++)to[px+2][py+j]=1;
to[px+2][py+m]=0;
for(int j=m;j>1;j--)to[px+1][py+j]=3;
to[px+1][py+1]=2;
for(int j=1;j<i-1;j++)to[px+2][py+j]=1;
to[px+2][py+i-1]=2;
break;
}
}else if(m>5&&sy<=m-2&&ty<=m-2){
solve(n,m-2,sx,sy,tx,ty,px,py);
for(int i=1;i<=n;i++)
if(to[px+i][py+m-2]==0){
to[px+i][py+m-2]=1;
for(int j=i;j<n;j++)to[px+j][py+m-1]=2;
to[px+n][py+m-1]=1;
for(int j=n;j>1;j--)to[px+j][py+m]=0;
to[px+1][py+m]=3;
for(int j=1;j<i-1;j++)to[px+j][py+m-1]=2;
to[px+i-1][py+m-1]=3;
break;
}else if(to[px+i][py+m-2]==2){
to[px+i][py+m-2]=1;
for(int j=i;j>1;j--)to[px+j][py+m-1]=0;
to[px+1][py+m-1]=1;
for(int j=1;j<n;j++)to[px+j][py+m]=2;
to[px+n][py+m]=3;
for(int j=n;j>i+1;j--)to[px+j][py+m-1]=0;
to[px+i+1][py+m-1]=3;
break;
}
}else if(n>5&&sx<=n-2&&tx<=n-2){
solve(n-2,m,sx,sy,tx,ty,px,py);
for(int i=1;i<=m;i++)
if(to[px+n-2][py+i]==1){
to[px+n-2][py+i]=2;
for(int j=i;j>1;j--)to[px+n-1][py+j]=3;
to[px+n-1][py+1]=2;
for(int j=1;j<m;j++)to[px+n][py+j]=1;
to[px+n][py+m]=0;
for(int j=m;j>i+1;j--)to[px+n-1][py+j]=3;
to[px+n-1][py+i+1]=0;
break;
}else if(to[px+n-2][py+i]==3){
to[px+n-2][py+i]=2;
for(int j=i;j<m;j++)to[px+n-1][py+j]=1;
to[px+n-1][py+m]=2;
for(int j=m;j>1;j--)to[px+n][py+j]=3;
to[px+n][py+1]=0;
for(int j=1;j<i-1;j++)to[px+n-1][py+j]=1;
to[px+n-1][py+i-1]=0;
break;
}
}else if(m>5&&sy>2&&ty>2){
solve(n,m-2,sx,sy-2,tx,ty-2,px,py+2);
for(int i=1;i<=n;i++)
if(to[px+i][py+3]==0){
to[px+i][py+3]=3;
for(int j=i;j<n;j++)to[px+j][py+2]=2;
to[px+n][py+2]=3;
for(int j=n;j>1;j--)to[px+j][py+1]=0;
to[px+1][py+1]=1;
for(int j=1;j<i-1;j++)to[px+j][py+2]=2;
to[px+i-1][py+2]=1;
break;
}else if(to[px+i][py+3]==2){
to[px+i][py+3]=3;
for(int j=i;j>1;j--)to[px+j][py+2]=0;
to[px+1][py+2]=3;
for(int j=1;j<n;j++)to[px+j][py+1]=2;
to[px+n][py+1]=1;
for(int j=n;j>i+1;j--)to[px+j][py+2]=0;
to[px+i+1][py+2]=1;
break;
}
}else if(n>5&&sx==1&&tx>3){
if(sy>2){
for(int i=sy;i<m;i++)to[px+1][py+i]=1;
to[px+1][py+m]=2;
for(int i=m;i>=sy;i--)to[px+2][py+i]=3;
to[px+2][py+sy-1]=0;
for(int i=sy-1;i>1;i--)to[px+1][py+i]=3;
to[px+1][py+1]=2;
for(int i=1;i<sy-2;i++)to[px+2][py+i]=1;
to[px+2][py+sy-2]=2;
solve(n-2,m,1,sy-2,tx-2,ty,px+2,py);
}else{
for(int i=sy;i>1;i--)to[px+1][py+i]=3;
to[px+1][py+1]=2;
for(int i=1;i<=sy;i++)to[px+2][py+i]=1;
to[px+2][py+sy+1]=0;
for(int i=sy+1;i<m;i++)to[px+1][py+i]=1;
to[px+1][py+m]=2;
for(int i=m;i>sy+2;i--)to[px+2][py+i]=3;
to[px+2][py+sy+2]=2;
solve(n-2,m,1,sy+2,tx-2,ty,px+2,py);
}
}else if(m>5&&sy==m&&ty<m-2){
if(sx>2){
for(int i=sx;i<n;i++)to[px+i][py+m]=2;
to[px+n][py+m]=3;
for(int i=n;i>=sx;i--)to[px+i][py+m-1]=0;
to[px+sx-1][py+m-1]=1;
for(int i=sx-1;i>1;i--)to[px+i][py+m]=0;
to[px+1][py+m]=3;
for(int i=1;i<sx-2;i++)to[px+i][py+m-1]=2;
to[px+sx-2][py+m-1]=3;
solve(n,m-2,sx-2,m-2,tx,ty,px,py);
}else{
for(int i=sx;i>1;i--)to[px+i][py+m]=0;
to[px+1][py+m]=3;
for(int i=1;i<=sx;i++)to[px+i][py+m-1]=2;
to[px+sx+1][py+m-1]=1;
for(int i=sx+1;i<n;i++)to[px+i][py+m]=2;
to[px+n][py+m]=3;
for(int i=n;i>sx+2;i--)to[px+i][py+m-1]=0;
to[px+sx+2][py+m-1]=3;
solve(n,m-2,sx+2,m-2,tx,ty,px,py);
}
}else if(n>5&&sx==n&&tx<n-2){
if(sy>2){
for(int i=sy;i<m;i++)to[px+n][py+i]=1;
to[px+n][py+m]=0;
for(int i=m;i>=sy;i--)to[px+n-1][py+i]=3;
to[px+n-1][py+sy-1]=2;
for(int i=sy-1;i>1;i--)to[px+n][py+i]=3;
to[px+n][py+1]=0;
for(int i=1;i<sy-2;i++)to[px+n-1][py+i]=1;
to[px+n-1][py+sy-2]=0;
solve(n-2,m,n-2,sy-2,tx,ty,px,py);
}else{
for(int i=sy;i>1;i--)to[px+n][py+i]=3;
to[px+n][py+1]=0;
for(int i=1;i<=sy;i++)to[px+n-1][py+i]=1;
to[px+n-1][py+sy+1]=2;
for(int i=sy+1;i<m;i++)to[px+n][py+i]=1;
to[px+n][py+m]=0;
for(int i=m;i>sy+2;i--)to[px+n-1][py+i]=3;
to[px+n-1][py+sy+2]=0;
solve(n-2,m,n-2,sy+2,tx,ty,px,py);
}
}else if(m>5&&sy==1&&ty>3){
if(sx>2){
for(int i=sx;i<n;i++)to[px+i][py+1]=2;
to[px+n][py+1]=1;
for(int i=n;i>=sx;i--)to[px+i][py+2]=0;
to[px+sx-1][py+2]=3;
for(int i=sx-1;i>1;i--)to[px+i][py+1]=0;
to[px+1][py+1]=1;
for(int i=1;i<sx-2;i++)to[px+i][py+2]=2;
to[px+sx-2][py+2]=1;
solve(n,m-2,sx-2,1,tx,ty-2,px,py+2);
}else{
for(int i=sx;i>1;i--)to[px+i][py+1]=0;
to[px+1][py+1]=1;
for(int i=1;i<=sx;i++)to[px+i][py+2]=2;
to[px+sx+1][py+2]=3;
for(int i=sx+1;i<n;i++)to[px+i][py+1]=2;
to[px+n][py+1]=1;
for(int i=n;i>sx+2;i--)to[px+i][py+2]=0;
to[px+sx+2][py+2]=1;
solve(n,m-2,sx+2,1,tx,ty-2,px,py+2);
}
}else if(n>5&&sx==2&&tx>3){
if(sy>1){
for(int i=sy;i<m;i++)to[px+2][py+i]=1;
to[px+2][py+m]=0;
for(int i=m;i>1;i--)to[px+1][py+i]=3;
to[px+1][py+1]=2;
for(int i=1;i<sy-1;i++)to[px+2][py+i]=1;
to[px+2][py+sy-1]=2;
solve(n-2,m,1,sy-1,tx-2,ty,px+2,py);
}else{
for(int i=sy;i>1;i--)to[px+2][py+i]=3;
to[px+2][py+1]=0;
for(int i=1;i<m;i++)to[px+1][py+i]=1;
to[px+1][py+m]=2;
for(int i=m;i>sy+1;i--)to[px+2][py+i]=3;
to[px+2][py+sy+1]=2;
solve(n-2,m,1,sy+1,tx-2,ty,px+2,py);
}
}else if(m>5&&sy==m-1&&ty<m-2){
if(sx>1){
for(int i=sx;i<n;i++)to[px+i][py+m-1]=2;
to[px+n][py+m-1]=1;
for(int i=n;i>1;i--)to[px+i][py+m]=0;
to[px+1][py+m]=3;
for(int i=1;i<sx-1;i++)to[px+i][py+m-1]=2;
to[px+sx-1][py+m-1]=3;
solve(n,m-2,sx-1,m-2,tx,ty,px,py);
}else{
for(int i=sx;i>1;i--)to[px+i][py+m-1]=0;
to[px+1][py+m-1]=1;
for(int i=1;i<n;i++)to[px+i][py+m]=2;
to[px+n][py+m]=3;
for(int i=n;i>sx+1;i--)to[px+i][py+m-1]=0;
to[px+sx+1][py+m-1]=3;
solve(n,m-2,sx+1,m-2,tx,ty,px,py);
}
}else if(n>5&&sx==n-1&&tx<n-2){
if(sy>1){
for(int i=sy;i<m;i++)to[px+n-1][py+i]=1;
to[px+n-1][py+m]=2;
for(int i=m;i>1;i--)to[px+n][py+i]=3;
to[px+n][py+1]=0;
for(int i=1;i<sy-1;i++)to[px+n-1][py+i]=1;
to[px+n-1][py+sy-1]=0;
solve(n-2,m,n-2,sy-1,tx,ty,px,py);
}else{
for(int i=sy;i>1;i--)to[px+n-1][py+i]=3;
to[px+n-1][py+1]=2;
for(int i=1;i<m;i++)to[px+n][py+i]=1;
to[px+n][py+m]=0;
for(int i=m;i>sy+1;i--)to[px+n-1][py+i]=3;
to[px+n-1][py+sy+1]=0;
solve(n-2,m,n-2,sy+1,tx,ty,px,py);
}
}else if(m>5&&sy==2&&ty>3){
if(sx>1){
for(int i=sx;i<n;i++)to[px+i][py+2]=2;
to[px+n][py+2]=3;
for(int i=n;i>1;i--)to[px+i][py+1]=0;
to[px+1][py+1]=1;
for(int i=1;i<sx-1;i++)to[px+i][py+2]=2;
to[px+sx-1][py+2]=1;
solve(n,m-2,sx-1,1,tx,ty-2,px,py+2);
}else{
for(int i=sx;i>1;i--)to[px+i][py+2]=0;
to[px+1][py+2]=3;
for(int i=1;i<n;i++)to[px+i][py+1]=2;
to[px+n][py+1]=1;
for(int i=n;i>sx+1;i--)to[px+i][py+2]=0;
to[px+sx+1][py+2]=1;
solve(n,m-2,sx+1,1,tx,ty-2,px,py+2);
}
}else assert(0);
}
int main(){
int n,m,sx,sy,tx,ty;
scanf("%d%d%d%d%d%d",&n,&m,&sx,&sy,&tx,&ty);
if(((sx+sy)%2==(tx+ty)%2)!=n*m%2)return puts("NIE"),0;
memset(to,-1,sizeof(to));
solve(n,m,sx,sy,tx,ty,0,0);
for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(i!=tx||j!=ty)assert(to[i][j]>=0&&to[i][j]<4);
// for(int i=1;i<=n;i++,puts(""))for(int j=1;j<=m;j++)
// if(to[i][j]==0)printf("↑");
// else if(to[i][j]==1)printf("→");
// else if(to[i][j]==2)printf("↓");
// else if(to[i][j]==3)printf("←");
// else printf("〇");
int x=sx,y=sy;
while(x!=tx||y!=ty){
int k=to[x][y];
putchar(ch[k]);
x+=dx[k],y+=dy[k];
}
putchar('\n');
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7688kb
input:
4 4 1 1 1 4
output:
DDPPGLGPPDDDLLL
result:
ok correct path
Test #2:
score: 0
Accepted
time: 1ms
memory: 3660kb
input:
4 4 3 2 2 3
output:
NIE
result:
ok no solution
Test #3:
score: -100
Dangerous Syscalls
input:
5 5 1 2 1 4