main.cpp

这是数据结构的一个课程设计.马踏棋盘,其中包含两种算法.一种只有一条路线,另一种有多条路线.还有设计文档.希望对大家有用.

#include<iostream.h>                   

int HTryX[]={2,1,-1,-2,-2,-1,1,2};             //数组记录八个可走方向的横坐标
int HTryY[]={1,2,2,1,-1,-2,-2,-1};             //数组记录八个可走方向的纵坐标
int chessboard[8][8];                          //定义了一个记录8*8的棋盘的数组函数
void Init();               //初始化棋盘,将各点置零函数
int outroad(int m,int n);     //计算出从该点出发，有多少个出口可走函数
bool check(int m,int n);        //判断某个方向是否可行函数
int dir(int m,int n);         //计算出从该点走,路径的最优选择函数
void print();           //打印棋盘结果函数


void Init()             //初始化棋盘，将所有的格子初始化为零
{int i,j;
    for(i=0;i<8;i++)
        for(j=0;j<8;j++)
            chessboard[i][j]=0;
}

int dir(int m,int n)       //计算出从该点走,路径的最优选择函数 
{                           
    int dir=0,num=8,k=0,i;    //dir为记录出口数最少的路径，num记录最大出口数,K为中间变量
    for(i=0;i<8;i++){
        if(check( (m+HTryX[i]),(n+HTryY[i]) )){     //判断某个方向是否可行
            k=outroad((m+HTryX[i]),(n+HTryY[i]));    //计算该方向的出口数目
            if( k &&(k<num) ) {                //求出口数最少
                num=k;               
                dir=i; 
            }
        }
    }
    if(dir==0) {                     //当step=63时，由于所有方向的出口数均为零，需要特殊考虑
        for(i=0;i<8;i++)
            if(check((m+HTryX[i]),(n+HTryY[i]))) return i;
    }
    return dir;        //返回最小出口数的方向
}

int outroad(int m,int n)     //计算出从该点出发，有多少个出口可走函数
{
    int i,out=0;           
    for(i=0;i<8;i++)         
        if(check((m+HTryX[i]),(n+HTryY[i]))) out++;   //如果某个方向可行，出口数+1
    return out;        //返回出口数
}

bool check(int m,int n) //判断该点是否已经走过，也即某个方向是否可行，可行返回1，否则返回0
{
    if( (m>=0)&&(m<8)&&(n>=0)&&(n<8)&&(chessboard[m][n]==0) ) return 1;  //没有出棋盘的边缘，并且没有走过，即为可行
    else return 0;
}

void print()  //将棋盘的信息打印，也即将走满的格子中的步数信息显示出来
{
    for(int i=0;i<8;i++){
        cout<<endl<<endl;
        for(int j=0;j<8;j++){
            cout.width(6);
            cout<<chessboard[i][j];
        }
    }
    cout<<endl<<endl;
}

void main()
{   cout<<endl;
    cout<<"----------------------------------马踏棋盘--------------------------------------"<<endl;
	cout<<"                                                                                "<<endl;
   int choice=0;
	do{ 
        cout<<endl<<"---------------------------------------------------------------------"<<endl;
		      cout<<"                                  MENU                               "<<endl;
              cout<<"                        <1>  输入初始位置                            "<<endl;
              cout<<"                        <2>  退出系统                                "<<endl;
              cout<<"---------------------------------------------------------------------"<<endl;
              cout<<"您的选择:";
        cin>>choice;
		int  x=0,y=0,step=1,i=0 ;
		Init();
        if(choice==1){
            cout<<endl<<"请输入横坐标(1--8)  x=";   //用户的输入过程
            cin>>x;
            cout<<"请输入纵坐标(1--8)  y=";
            cin>>y;
			x--;y--;
			chessboard[x][y]=step;                 //记录初始位置，将该点的坐标定义为步数step
            for(step=2;step<65;step++){        // 每一步
                i=dir(x,y);      //求从某点出发可走的方向中，出口数最小的方向
                x+=HTryX[i];       //前进一步
                y+=HTryY[i];
                chessboard[x][y]=step;
				 
				 print(); 
            }
                      
        }
    }while(choice!=2);
}