knight.cpp

马的Hamilton周游路线问题

#include <stdio.h>
#include <iostream>

using namespace std;


//grid是表示整数对的结构
typedef struct {
	int x;
	int y;
}grid;

//二维数组的构造

void Make2DArray1(int **a,int m, int n)
{
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
			a[i][j] = 0;
}

void Make2DArray2(grid **link,int m, int n)
{
	for(int i=0;i<m;i++)
		for(int j=0;j<n;j++)
		{
			link[i][j].x=0;
			link[i][j].y=0;
		}
}

//odd函数
bool odd(int x)
{
	if(x%2 ==0) return 0;
	else return 1;
}
//用一个类Knight实现算法
class Knight{
public:
	Knight(int m, int n);
	~Knight(){};
	void out();
public:
	int m,n;
	grid *b66,*b68,*b86,*b88,*b810,*b108,*b1010,*b1012,*b1210,**link;
	int pos(int x, int y,int col);
	void change(int m, int n, int **a, grid *b);
	void construct(int m, int n, int offx, int offy, int col, grid *b);
	void base_answer(int mm, int nn, int offx, int offy);
	bool comb(int mm, int nn, int offx, int offy);
};



//构造函数读入基础数据，初始化各数组
Knight::Knight(int mm, int nn)
{
	int i,j,k;
	m = mm;
	n = nn;
	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];
	//初始化二维数组a和link
	link = new grid*[m];
	for(k=0;k<m;k++)
	{
		link[k] = new grid[n];
	}
	
	int **a = new int*[10];
	for(k=0;k<10;k++)
	{
		a[k] = new int[12];
	}
    
	Make2DArray2(link,m,n);
	Make2DArray1(a,10,12);
		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},
		};
		for(i=0;i<6;i++)
			for(j=0;j<6;j++)
				a[i][j]=a66[i][j];
			change(6,6,a,b66);
			
			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};	
			for(i=0;i<6;i++)
				for(j=0;j<8;j++)
					a[i][j]=a68[i][j];
				change(6,8,a,b68);
				change(8,6,a,b86);
				
				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};
				for(i=0;i<8;i++)
					for(j=0;j<8;j++)
						a[i][j]=a88[i][j];
					change(8,8,a,b88);
					
					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};
					for(i=0;i<8;i++)
						for(j=0;j<10;j++)
							a[i][j]=a810[i][j];
						change(8,10,a,b810);
						change(10,8,a,b108);
						
						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};
						for(i=0;i<10;i++)
							for(j=0;j<10;j++)
								a[i][j]=a1010[i][j];
							change(10,10,a,b1010);
							
							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};
							for(i=0;i<10;i++)
								for(j=0;j<12;j++)
									a[i][j]=a1012[i][j];
								change(10,12,a,b1012);
								change(12,10,a,b1210);
}



//change用于将读入的基础棋盘的Hamilton回路转化为网格数据

void Knight::change(int m, int n, int **a, grid *b)
{
	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;
			}
	}
}

//分治法的主体由如下算法 comb 给出

bool Knight::comb(int mm, int nn, int offx, int offy)
{
	int mm1, mm2,nn1,nn2;
	int x[8],y[8],p[8];
	if(odd(mm) || odd(nn) || mm-nn > 2 || nn-mm > 2 || mm < 6 || nn <6) return 1;
	if(mm < 12 || nn < 12)//基础解
	{
		base_answer(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;
	//分割步
	comb(mm1,nn1,offx,offy);
	comb(mm1,nn2,offx,offy+nn1);
	comb(mm2,nn1,offx+mm1,offy);
	comb(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];
	}
	return 0;
}


//base_answer是根据基础解构造子棋盘的结构化的Hamilton回路

void Knight::base_answer(int mm, int nn, int offx, int offy)
{
	if(mm == 6 && nn == 6) construct(mm,nn,offx,offy,n,b66);
	if(mm == 6 && nn == 8) construct(mm,nn,offx,offy,n,b68);
	if(mm == 8 && nn == 6) construct(mm,nn,offx,offy,n,b86);
	if(mm == 8 && nn == 8) construct(mm,nn,offx,offy,n,b88);
	if(mm == 8 && nn == 10) construct(mm,nn,offx,offy,n,b810);
	if(mm == 10 && nn == 8) construct(mm,nn,offx,offy,n,b108);
	if(mm == 10 && nn == 10) construct(mm,nn,offx,offy,n,b1010);
	if(mm == 10 && nn == 12) construct(mm,nn,offx,offy,n,b1012);
	if(mm == 12 && nn == 10) construct(mm,nn,offx,offy,n,b1210);
}


//实质性的构造有算法bulid完成

void Knight::construct(int m, int n, int offx, int offy, int col, grid *b)
{
	int i,p,q,k=m*n;
	for(i=0;i<k;i++)
	{
		int x1 = offx+b[i].x, y1 = offy+b[i].y;
		int x2 = offx+b[(i+1)%k].x, y2 = offy+b[(i+1)%k].y;
		p = pos(x1,y1,col);q = pos(x2,y2,col);
		link[x1][y1].x=q;link[x2][y2].y=p;	 
		
	}
}


//pos用于表示计算棋盘方格的编号，棋盘方格各行从上到下，各列从左到右依次编号为0,1....,mn-1

int Knight::pos(int x, int y, int col)
{
	return col*x+y;
}

//由out按要求输出计算出的结构化的Hamilton回路

void Knight::out()
{
	int i,j,k,x,y,p,**a;
	a = new int*[m];
	for(k=0;k<m;k++)
	{
		a[k] = new int[n];
	}
	Make2DArray1(a,m,n);
	if(comb(m,n,0,0)) return;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
			a[i][j]=0;
		i=0;j=0;k=2;a[0][0]=1;
		cout<<"(0,0)"<<" ";
		for(p=1;p<m*n;p++)
		{
			x=link[i][j].x; y=link[i][j].y;
			i=x/n;j=x%n;
			if(a[i][j]>0) 
			{
				i=y/n;
				j=y%n;
			}
			a[i][j] = k++;
			cout<<"("<<i<<","<<j<<")"<<" ";
			if((k-1)%n == 0) cout<<endl;
		}
		cout<<endl;
		for(i=0;i<m;i++)
		{
			for(j=0;j<n;j++)
				cout<<a[i][j]<<" ";
			cout<<endl;
		}
}



//主函数


int main()
{
	freopen("input.txt","r",stdin);
	int m,n,k;//m,n分别表示棋盘有m行,每行有n个格子
	cin>>m>>n;
	Knight knight(m,n);
	freopen("output.txt","w",stdout);
	knight.out();
	
	return 0;
}