horse.cpp

数据结构中的马塌棋盘问题

#include<stdio.h>
#include<iomanip.h>
int deg[8][8]={{2,3,4,4,4,4,3,2},{3,4,6,6,6,6,4,3},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{3,4,6,6,6,6,4,3},{2,3,4,4,4,4,3,2}};
int trai[8][8];
int Htry[2][8]={-2,-1,1,2,2,1,-1,-2,1,2,2,1,-1,-2,-2,-1};
int i,j,s=1;
void line()//由当前位置(,j)一位跳的位置
{
	int min=8,p,q;
	deg[i][j]=0;
	trai[i][j]=s++;
	for(int k=0;k<8;k++)
	{
		int m=i+Htry[0][k];
		int n=j+Htry[1][k];
		if(n>=0&&n<8&&m>=0&&m<8&&deg[m][n]!=0)
		{
			deg[m][n]--;
			if(min>=deg[m][n])
			{
				min=deg[m][n];
				p=i+Htry[0][k];
				q=j+Htry[1][k];
			}
		}
	}
    i=p;
	j=q;
}




degree();
void main()
{
	degree();//调出结点度数表
	cout<<"请输入你要选的初始位置:i=";
	cin>>i;
	cout<<"j=";
	cin>>j;

   for(int foot=1;foot<=64;foot++)//out loop 64 times
	   line();
   cout<<"马行走的路线是下表:"<<endl;
  
   printf("=================================\n");

   for(i=0;i<8;i++)
   { 
	   for(j=0;j<8;j++)
	   cout<<"|"<<setw(3)<<trai[i][j];
	   cout<<"|"<<endl;
	   printf("=================================\n");
   }
}


degree()
{
	printf("马可能走的位置时的结点度数:\n");
	printf("=================================\n");
	printf("| 2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |\n");
	printf("---------------------------------\n");
	printf("| 3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |\n");
	printf("---------------------------------\n");
	printf("| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |\n");
	printf("---------------------------------\n");
	printf("| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |\n");
	printf("---------------------------------\n");
	printf("| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |\n");
	printf("---------------------------------\n");
	printf("| 4 | 6 | 8 | 8 | 8 | 8 | 6 | 4 |\n");
	printf("---------------------------------\n");
	printf("| 3 | 4 | 6 | 6 | 6 | 6 | 4 | 3 |\n");
	printf("---------------------------------\n");
	printf("| 2 | 3 | 4 | 4 | 4 | 4 | 3 | 2 |\n");
	printf("=================================\n");
	return 0;
  }