knight.cpp

求马的哈密顿回路,在国际相棋棋局上,一只马要经过每个点,且仅经过一次,棋局可以是非常大,要求输出马经过的所有点及路径.

#include<iostream>
#include <fstream>
#include <math.h>
//#include<ctime>
using namespace std;

typedef struct
{
	int x;
	int y;
}grid;

	int a66[6][6]={1,30,33,16,3,24,
		32,17,2,23,34,15,
		29,36,31,14,25,4,
		18,9,6,35,22,13,
		7,28,11,20,5,26,
		10,19,8,27,12,21};

	int a68[6][8]={1,10,31,40,21,14,29,38,
		32,41,2,11,30,39,22,13,
		9,48,33,20,15,12,37,28,
		42,3,44,47,6,25,18,23,
		45,8,5,34,19,16,27,36,
		4,43,46,7,26,35,24,17};

	int a88[8][8]={1,46,17,50,3,6,31,52,
		18,49,2,7,30,51,56,5,
		45,64,47,16,27,4,53,32,
		48,19,8,29,10,55,26,57,
		63,44,11,22,15,28,33,54,
		12,41,20,9,36,23,58,25,
		43,62,39,14,21,60,37,34,
		40,13,42,61,38,35,24,59};

	int a810[8][10]={1,46,37,66,3,48,35,68,5,8,
		38,65,2,47,36,67,4,7,34,69,
		45,80,39,24,49,18,31,52,9,6,
		64,23,44,21,30,15,50,19,70,33,
		79,40,25,14,17,20,53,32,51,10,
		26,63,22,43,54,29,16,73,58,71,
		41,78,61,28,13,76,59,56,11,74,
		62,27,42,77,60,55,12,75,72,57};

	int a1010[10][10]={1,54,69,66,3,56,39,64,5,8,
		68,71,2,55,38,65,4,7,88,63,
		53,100,67,70,57,26,35,40,9,6,
		72,75,52,27,42,37,58,87,62,89,
		99,30,73,44,25,34,41,36,59,10,
		74,51,76,31,28,43,86,81,90,61,
		77,98,29,24,45,80,33,60,11,92,
		50,23,48,79,32,85,82,91,14,17,
		97,78,21,84,95,46,19,16,93,12,
		22,49,96,47,20,83,94,13,18,15};

	int a1012[10][12]={1,4,119,100,65,6,69,102,71,8,75,104,
		118,99,2,5,68,101,42,7,28,103,72,9,
		3,120,97,64,41,66,25,70,39,74,105,76,
		98,117,48,67,62,43,40,27,60,29,10,73,
		93,96,63,44,47,26,61,24,33,38,77,106,
		116,51,94,49,20,23,46,37,30,59,34,11,
		95,92,115,52,45,54,21,32,35,80,107,78,
		114,89,50,19,22,85,36,55,58,31,12,81,
		91,18,87,112,53,16,57,110,83,14,79,108,
		88,113,90,17,86,111,84,15,56,109,82,13};

class knight
{
public:
	knight(int x,int y)
	{
//		cout<<"knight1"<<endl;
		int i,j,**a;
		m=x;n=y;	
		a=new int *[10];//赋值用的数组
		for(i=0;i<10;i++)
		{
			a[i]=new int [12];
		}
//		cout<<"knight2"<<endl;
		b66=new grid[36];
		b68=new grid[48];
		b86=new grid[48];
		b88=new grid[64];
		b810=new grid[80];
		b108=new grid[80];
		b1010=new grid[100];
		b1012=new grid[120];
		b1210=new grid[120];

		link=new grid *[m];
		for(i=0;i<m;i++)
		{
			link[i]=new grid[n];
		}
//		cout<<"knight3"<<endl;

		////////////////////以下是对b数组的赋值
		for(i=0;i<6;i++)
			for(j=0;j<6;j++)
				a[i][j]=a66[i][j];
		makeb(6,6,a,b66);
//		cout<<"knight4"<<endl;
		for(i=0;i<6;i++)
			for(j=0;j<8;j++)
				a[i][j]=a68[i][j];
		makeb(6,8,a,b68); 
		makeb(8,6,a,b86);

		for(i=0;i<8;i++)
			for(j=0;j<8;j++)
				a[i][j]=a88[i][j];
		makeb(8,8,a,b88);

		for(i=0;i<8;i++)
			for(j=0;j<10;j++)
				a[i][j]=a810[i][j];
		makeb(8,10,a,b810);	
		makeb(10,8,a,b108);

		for(i=0;i<10;i++)
			for(j=0;j<10;j++)
				a[i][j]=a1010[i][j];
		makeb(10,10,a,b1010);

		for(i=0;i<10;i++)
			for(j=0;j<12;j++)
				a[i][j]=a1012[i][j];
		makeb(10,12,a,b1012);
		makeb(12,10,a,b1210);		
//		cout<<"knight"<<endl;

	}
	
	grid *b66,*b68,*b86,*b88,*b810,*b108,*b1010,*b1012,*b1210,**link;
	int m,n;

	int pos(int x,int y,int col)
	{
		return col*x+y;
	}
	
	void makeb(int m,int n,int **a,grid *b)
	{
//		cout<<"step1"<<endl;
		int i,j,k=m*n;
		if(m<n)
		{
			for(i=0;i<m;i++)
				for(j=0;j<n;j++)
				{
					int p=a[i][j]-1;
					b[p].x=i;
					b[p].y=j;
				}
		}
		else
		{
			for(i=0;i<m;i++)
				for(j=0;j<n;j++)
				{
					int p=a[j][i]-1;
					b[p].x=i;
					b[p].y=j;
				}
		}
//		cout<<"step2"<<endl;
	}

	void build(int m,int n,int offx,int offy,int col,grid *b)
	{
//		cout<<"build1"<<endl;
		int i,k=m*n;
		for(i=0;i<k;i++)
		{
			int x1=offx+b[i].x,
				y1=offy+b[i].y,
				x2=offx+b[(i+1)%k].x,
				y2=offy+b[(i+1)%k].y;
			link[x1][y1].x=pos(x2,y2,col);
			link[x2][y2].y=pos(x1,y1,col);
		}
//		cout<<"build2"<<endl;
	}

	void base(int mm,int nn,int offx,int offy)
	{
//		cout<<"base1"<<endl;
		if(mm==6&&nn==6) build(mm,nn,offx,offy,n,b66);
		if(mm==6&&nn==8) build(mm,nn,offx,offy,n,b68);
		if(mm==8&&nn==6) build(mm,nn,offx,offy,n,b86);
		if(mm==8&&nn==8) build(mm,nn,offx,offy,n,b88);
		if(mm==8&&nn==10) build(mm,nn,offx,offy,n,b810);
		if(mm==10&&nn==8) build(mm,nn,offx,offy,n,b108);
		if(mm==10&&nn==10) build(mm,nn,offx,offy,n,b1010);
		if(mm==10&&nn==12) build(mm,nn,offx,offy,n,b1012);
		if(mm==12&&nn==10) build(mm,nn,offx,offy,n,b1210);
//		cout<<"base2"<<endl;
	}

	bool comp(int mm,int nn,int offx,int offy)
	{
//		cout<<"comp1"<<endl;
		int mm1,mm2,nn1,nn2;
		int x[8],y[8],p[8];
		if(mm-nn>2||nn-mm>2||mm<6||nn<6) return 1;
		if(mm<12||nn<12)
		{
			base(mm,nn,offx,offy);
			return 0;
		}
		mm1=mm/2;
		if(mm%4>0)
			mm1--;
		mm2=mm-mm1;
		nn1=nn/2;
		if(nn%4>0)
			nn1--;
		nn2=nn-nn1;

		comp(mm1,nn1,offx,offy);
		comp(mm1,nn2,offx,offy+nn1);
		comp(mm2,nn1,offx+mm1,offy);
		comp(mm2,nn2,offx+mm1,offy+nn1);

		x[0]=offx+mm1-1; y[0]=offy+nn1-3;
		x[1]=x[0]-1;y[1]=y[0]+2;
		x[2]=x[1]-1;y[2]=y[1]+2;
		x[3]=x[2]+2;y[3]=y[2]-1;
		x[4]=x[3]+1;y[4]=y[3]+2;
		x[5]=x[4]+1;y[5]=y[4]-2;
		x[6]=x[5]+1;y[6]=y[5]-2;
		x[7]=x[6]-2;y[7]=y[6]+1;

		for(int i=0;i<8;i++)
			p[i]=pos(x[i],y[i],n);
		for(i=1;i<8;i+=2)
		{
			int j1=(i+1)%8,j2=(i+2)%8;
			if(link[x[i]][y[i]].x==p[i-1])
				link[x[i]][y[i]].x=p[j1];
			else
				link[x[i]][y[i]].y=p[j1];

			if(link[x[j1]][y[j1]].x==p[j2])
				link[x[j1]][y[j1]].x=p[i];
			else
				link[x[j1]][y[j1]].y=p[i];	
		}
//		cout<<"comp2"<<endl;
		return 0;

	}
};

void main()
{
	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	ofstream out("output.txt");

	int m,n;
	in>>m>>n;
	knight k_night(m,n);
	int i,j,k,x,y,p,**output;

	output=new int *[m];
	for(i=0;i<m;i++)
	{
		output[i]=new int [n];
	}
	
	if(k_night.comp(k_night.m,k_night.n,0,0))
		return;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			output[i][j]=0;

	i=0;j=0;k=2;output[0][0]=1;
	out<<"(0,0)"<<" ";
	for(p=1;p<m*n;p++)
	{
		x=k_night.link[i][j].x;
		y=k_night.link[i][j].y;
		i=x/n;
		j=x%n;
		if(output[i][j]>0)
		{
			i=y/n;
			j=y%n;
		}
		output[i][j]=k++;
		out<<"("<<i<<","<<j<<") ";
		if((k-1)%n==0)
			out<<endl;
	}

	out<<endl;
	for(i=0;i<m;i++)
	{
		for(j=0;j<n;j++)
			out<<output[i][j]<<" ";
		out<<endl;
	}
}