1198: Solitaire

もうすこし真面目に考えてからソースを書くことにします

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
struct wolf{
	int depth;
	int r[4];
	int c[4];
	wolf(){}
	wolf(int a,int b,int C,int d,int e,int f,int g,int h,int D){
		r[0]=a;
		c[0]=b;
		r[1]=C;
		c[1]=d;
		r[2]=e;
		c[2]=f;
		r[3]=g;
		c[3]=h;
		depth=D;
	}
};
bool bfs[8][8][8][8][8][8][8][8];
pair<int,int> p[4];
int main(){
	int a,b,c,d,e,f,g,h;
	scanf("%d%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&g,&h);
	a--;
	b--;
	c--;
	d--;
	e--;
	f--;
	g--;
	h--;
	p[0]=make_pair(a,b);
	p[1]=make_pair(c,d);
	p[2]=make_pair(e,f);
	p[3]=make_pair(g,h);
	std::sort(p,p+4);
	queue<wolf>Q;
	Q.push(wolf(p[3].first,p[3].second,p[2].first,p[2].second,p[1].first,p[1].second,p[0].first,p[0].second,0));
	scanf("%d%d%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f,&g,&h);
	a--;
	b--;
	c--;
	d--;
	e--;
	f--;
	g--;
	h--;
	p[0]=make_pair(a,b);
	p[1]=make_pair(c,d);
	p[2]=make_pair(e,f);
	p[3]=make_pair(g,h);
	std::sort(p,p+4);
	while(Q.size()){
		wolf at=Q.front();
		Q.pop();
		if(at.r[0]<at.r[1]||(at.r[0]==at.r[1]&&at.c[0]<at.c[1])){
			int m=at.r[0];
			int n=at.c[0];
			at.r[0]=at.r[1];
			at.r[1]=m;
			at.c[0]=at.c[1];
			at.c[1]=n;
		}
		if(at.r[0]<at.r[2]||(at.r[0]==at.r[2]&&at.c[0]<at.c[2])){
			int m=at.r[0];
			int n=at.c[0];
			at.r[0]=at.r[2];
			at.r[2]=m;
			at.c[0]=at.c[2];
			at.c[2]=n;
		}
		if(at.r[0]<at.r[3]||(at.r[0]==at.r[3]&&at.c[0]<at.c[3])){
			int m=at.r[0];
			int n=at.c[0];
			at.r[0]=at.r[3];
			at.r[3]=m;
			at.c[0]=at.c[3];
			at.c[3]=n;
		}
		if(at.r[1]<at.r[2]||(at.r[1]==at.r[2]&&at.c[1]<at.c[2])){
			int m=at.r[1];
			int n=at.c[1];
			at.r[1]=at.r[2];
			at.r[2]=m;
			at.c[1]=at.c[2];
			at.c[2]=n;
		}
		if(at.r[1]<at.r[3]||(at.r[1]==at.r[3]&&at.c[1]<at.c[3])){
			int m=at.r[1];
			int n=at.c[1];
			at.r[1]=at.r[3];
			at.r[3]=m;
			at.c[1]=at.c[3];
			at.c[3]=n;
		}
		if(at.r[2]<at.r[3]||(at.r[2]==at.r[3]&&at.c[2]<at.c[3])){
			int m=at.r[2];
			int n=at.c[2];
			at.r[2]=at.r[3];
			at.r[3]=m;
			at.c[2]=at.c[3];
			at.c[3]=n;
		}
		int O=at.depth+1;
		if(bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]])continue;
		bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]=true;
		if(at.depth==8)continue;
	//	if(at.r[0]==3&&at.c[0]==5&&at.c[1]==5&&at.c[2]==2)printf("%d %d %d %d %d %d %d %d\n",at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3]);
		bool k;
		bool z;
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.r[j]==at.r[0]-1&&at.c[j]==at.c[0])k=true;
			if(at.r[j]==at.r[0]-2&&at.c[j]==at.c[0])z=true;
		}
		if(!z&&k&&at.r[0]>=2&&!bfs[at.r[0]-2][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0]-2,at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}else if(!k&&at.r[0]>=1&&!bfs[at.r[0]-1][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0]-1,at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.r[j]==at.r[0]+1&&at.c[j]==at.c[0])k=true;
			if(at.r[j]==at.r[0]+2&&at.c[j]==at.c[0])z=true;
		}
		if(!z&&k&&at.r[0]<6&&!bfs[at.r[0]+2][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0]+2,at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}else if(!k&&at.r[0]<7&&!bfs[at.r[0]+1][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0]+1,at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.c[j]==at.c[0]-1&&at.r[j]==at.r[0])k=true;
			if(at.c[j]==at.c[0]-2&&at.r[j]==at.r[0])z=true;
		}
		if(!z&&k&&at.c[0]>=2&&!bfs[at.r[0]][at.c[0]-2][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0]-2,at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}else if(!k&&at.c[0]>=1&&!bfs[at.r[0]][at.c[0]-1][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0]-1,at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.c[j]==at.c[0]+1&&at.r[j]==at.r[0])k=true;
			if(at.c[j]==at.c[0]+2&&at.r[j]==at.r[0])z=true;
		}
		if(!z&&k&&at.c[0]<6&&!bfs[at.r[0]][at.c[0]+2][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0]+2,at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}else if(!k&&at.c[0]<7&&!bfs[at.r[0]][at.c[0]+1][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0]+1,at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}

		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.r[j]==at.r[1]-1&&at.c[j]==at.c[1])k=true;
			if(at.r[j]==at.r[1]-2&&at.c[j]==at.c[1])z=true;
		}
		if(!z&&k&&at.r[1]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]-2][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1]-2,at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}else if(!k&&at.r[1]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]-1][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1]-1,at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.r[j]==at.r[1]+1&&at.c[j]==at.c[1])k=true;
			if(at.r[j]==at.r[1]+2&&at.c[j]==at.c[1])z=true;
		}
		if(!z&&k&&at.r[1]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]+2][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1]+2,at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}else if(!k&&at.r[1]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]+1][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1]+1,at.c[1],at.r[2],at.c[2],at.r[3],at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.c[j]==at.c[1]-1&&at.r[j]==at.r[1])k=true;
			if(at.c[j]==at.c[1]-2&&at.r[j]==at.r[1])z=true;
		}
		if(!z&&k&&at.c[1]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]-2][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1]-2,at.r[2],at.c[2],at.r[3],at.c[3],O));
		}else if(!k&&at.c[1]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]-1][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1]-1,at.r[2],at.c[2],at.r[3],at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.c[j]==at.c[1]+1&&at.r[j]==at.r[1])k=true;
			if(at.c[j]==at.c[1]+2&&at.r[j]==at.r[1])z=true;
		}
		if(!z&&k&&at.c[1]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]+2][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1]+2,at.r[2],at.c[2],at.r[3],at.c[3],O));
		}else if(!k&&at.c[1]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]+1][at.r[2]][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1]+1,at.r[2],at.c[2],at.r[3],at.c[3],O));
		}

		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.r[j]==at.r[2]-1&&at.c[j]==at.c[2])k=true;
			if(at.r[j]==at.r[2]-2&&at.c[j]==at.c[2])z=true;
		}
		if(!z&&k&&at.r[2]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]-2][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2]-2,at.c[2],at.r[3],at.c[3],O));
		}else if(!k&&at.r[2]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]-1][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2]-1,at.c[2],at.r[3],at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.r[j]==at.r[2]+1&&at.c[j]==at.c[2])k=true;
			if(at.r[j]==at.r[2]+2&&at.c[j]==at.c[2])z=true;
		}
		if(!z&&k&&at.r[2]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]+2][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2]+2,at.c[2],at.r[3],at.c[3],O));
		}else if(!k&&at.r[2]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]+1][at.c[2]][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2]+1,at.c[2],at.r[3],at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.c[j]==at.c[2]-1&&at.r[j]==at.r[2])k=true;
			if(at.c[j]==at.c[2]-2&&at.r[j]==at.r[2])z=true;
		}
		if(!z&&k&&at.c[2]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]-2][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2]-2,at.r[3],at.c[3],O));
		}else if(!k&&at.c[2]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]-1][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2]-1,at.r[3],at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.c[j]==at.c[2]+1&&at.r[j]==at.r[2])k=true;
			if(at.c[j]==at.c[2]+2&&at.r[j]==at.r[2])z=true;
		}
		if(!z&&k&&at.c[2]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]+2][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2]+2,at.r[3],at.c[3],O));
		}else if(!k&&at.c[2]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]+1][at.r[3]][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2]+1,at.r[3],at.c[3],O));
		}

		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.r[j]==at.r[3]-1&&at.c[j]==at.c[3])k=true;
			if(at.r[j]==at.r[3]-2&&at.c[j]==at.c[3])z=true;
		}
		if(!z&&k&&at.r[3]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]-2][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3]-2,at.c[3],O));
		}else if(!k&&at.r[3]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]-1][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3]-1,at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.r[j]==at.r[3]+1&&at.c[j]==at.c[3])k=true;
			if(at.r[j]==at.r[3]+2&&at.c[j]==at.c[3])z=true;
		}
		if(!z&&k&&at.r[3]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]+2][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3]+2,at.c[3],O));
		}else if(!k&&at.r[3]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]+1][at.c[3]]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3]+1,at.c[3],O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.c[j]==at.c[3]-1&&at.r[j]==at.r[3])k=true;
			if(at.c[j]==at.c[3]-2&&at.r[j]==at.r[3])z=true;
		}
		if(!z&&k&&at.c[3]>=2&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]-2]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3]-2,O));
		}else if(!k&&at.c[3]>=1&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]-1]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3]-1,O));
		}
		k=false;
		z=false;
		for(int j=0;j<4;j++){
			if(at.c[j]==at.c[3]+1&&at.r[j]==at.r[3])k=true;
			if(at.c[j]==at.c[3]+2&&at.r[j]==at.r[3])k=true;
		}
		if(!z&&k&&at.c[3]<6&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]+2]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3]+2,O));
		}else if(!k&&at.c[3]<7&&!bfs[at.r[0]][at.c[0]][at.r[1]][at.c[1]][at.r[2]][at.c[2]][at.r[3]][at.c[3]+1]){
			Q.push(wolf(at.r[0],at.c[0],at.r[1],at.c[1],at.r[2],at.c[2],at.r[3],at.c[3]+1,O));
		}
		if(bfs[p[3].first][p[3].second][p[2].first][p[2].second][p[1].first][p[1].second][p[0].first][p[0].second])break;
	}
	if(bfs[p[3].first][p[3].second][p[2].first][p[2].second][p[1].first][p[1].second][p[0].first][p[0].second])printf("YES\n");
	else printf("NO\n");
}