mtqp.cpp

马踏棋盘问题：国际象棋中的马

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

int DirX[]={2,1,-1,-2,-2,-1,1,2};
int DirY[]={1,2,2,1,-1,-2,-2,-1};
int Board[8][8];

typedef struct
{
 int r;
 int c;
}PosType;//定义位置坐标类型


void DesignerInfo()
{
 printf("****************** 设计信息 *******************\n");
 printf("*  课题：马踏棋盘                             *\n");
 printf("*  姓名：寒 冬                                *\n");
 printf("*  学号：20022319                             *\n");
 printf("*  发开：数据结构                             *\n");
 printf("***********************************************\n");
}

int ExitNum(int i,int j,int s,int a[])
{
//求（i,j）的出口数和各出口号于a[]，s是顺序选择着法的开始序号
int i1,j1,k,count;
for(count=k=0;k<8;k++)
	{
        i1=i+DirX[(s+k)%8];j1=j+DirY[(s+k)%8];
        if(i1>=0&&i1<8&&j1>=0&&j1<8&&Board[i1][j1]==0)
        a[count++]=(s+k)%8;
	}
return count;
}


int NextExit(int i,int j,int s)//选下一出口，从s着法顺序选择
{
int m,k,kk,min,a[8],b[8],temp;
m=ExitNum(i,j,s,a); //确定(i,j)的出口个数
if(m==0) return -1;//没有出口
for(min=9,k=0;k<m;k++)
	{//逐一考察各出口
        temp=ExitNum(i+DirX[a[k]],j+DirY[a[k]],s,b);
        if(temp<min)
		{//找出有最少出口的出口
        min=temp;kk=a[k];
		}
	}
return kk;//返回选中的着法
}
 


void main()
{
int sx,sy,i,j,step,no,start; char choices;
PosType StartPos;
start=0;      //从0号着法开始顺序检查
DesignerInfo();
			printf("input start position:\n");
			scanf("%d%d",&StartPos.r,&StartPos.c);
			sx=StartPos.r-1;sy=StartPos.c-1;
           do{
               for(i=0;i<8;i++)
                 for(j=0;j<8;j++)
					Board[i][j]=0;//清棋盘
					Board[sx][sy]=1;//将初始位置置为第一步
					i=sx;j=sy;
						for(step=2;step<=64;step++)
						{
							if((no=NextExit(i,j,start))==-1) break;
							i+=DirX[no];//前进一步
							j+=DirY[no];
							Board[i][j]=step;
						}
					if(step>64) break;
					start++;
		   }
			while(step<=64);
			for(i=0;i<8;i++)
			for(j=0;j<8;j++)
			{
				printf("   %4d",Board[i][j]);
				if(j==7) printf("\n\n");
			}
		
           
}