QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#80597#3816. Home alone: Johnny lost in New YorkfansizheRE 2ms7688kbC++239.0kb2023-02-24 13:24:152023-02-24 13:24:18

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-24 13:24:18]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:7688kb
  • [2023-02-24 13:24:15]
  • 提交

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;
}

详细

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

output:


result: