main2.cpp

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

#include<iostream.h>
#include <stdio.h>
#define N 8    
int w=0;                         //第几条可走路径
int HTryX[8]={-2,-1,1,2, 2, 1,-1,-2};
int HTryY[8]={ 1,2, 2,1,-1,-2,-2,-1};  //在（i,j）位置处的8个可能走的位置
int chess[N*N]={0};      //  走过的相应的点的赋值
int a[N*N+1][3]={0};     //路径所经过点的记录
int dir[N][N][8];      //（i,j）点的八个可能走的方向
int step=1;         //走过的步数
char c='y';
int weight[N][N];        //每个点的权值
void outroad(); //计算各点的权值 
void mixdir();//求出各点的最佳方向序列，即优先向权值小的方向 
void print();//输出路径走过的序号 
int  check(int i,int j);//检查(i,j)是否在棋盘内 

void outroad()//计算各点的权值，将权值存在weight[i][j]中 
{
 int i,j,k;
 for(i=1;i<=N;i++)
 for(j=1;j<=N;j++)
 for(k=0;k<N;k++) 
  { 
   int x,y;
   x=i+HTryX[k];
   y=j+HTryY[k];//下一步走的点  
   if(x>=1&&x<=N&&y>=1&&y<=N)
      weight[i-1][j-1]++;//权值 
   }
}

int  check(int i,int j)//检查(i,j)是否在棋盘内，在返回1，不在返回0 
{
if(i<1||i>8||j<1||j>8)
 return 0;return 1;
}

void mixdir()//求出各点的最佳方向序列，即优先向权值小的方向 
{
int i,j,k,m,n1,n2,x1,y1,x2,y2,way_1,way_2;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
 {   for(k=0;k<8;k++)dir[i][j][k]=k;
  for(k=0;k<8;k++)        {
for(m=k+1;m<8;m++)//对每个方向考察看有没有更好的    
  { 
      way_1=dir[i][j][k];
      x1=i+HTryX[way_1];
      y1=j+HTryY[way_1];//k方向时的下一个点 
      way_2=dir[i][j][m]; 
      x2=i+HTryX[way_2];
      y2=j+HTryY[way_2];//m方向时的下一个点 
      n1=check(x1+1,y1+1); 
      n2=check(x2+1,y2+1);//判断n1,n2是否在棋盘内 　
      if(( n1==0 && n2)||( n1 && n2&&weight[x1][y1]>weight[x2][y2]))//k方向不可达到，而m方向可达到 　||　 都可达到，但m方向权值小             
        {
         dir[i][j][k]=way_2;dir[i][j][m]=way_1;//交换两个方向值，将k走更好的一步棋（即权值小的一步） 
        } 
       }              }  
     }
}
void print()//输出路径走过的序号 
{
 int x,y;
 cout<<endl<<"-----------------------第"<<++w<<"条路径----------------------------"<<endl;//输出是第w条路径的序号 
 for(x=1;x<N+1;x++)
  {
   cout<<endl; 
   for(y=1;y<N+1;y++)
   {cout.width(6);
	   cout<<chess[(x-1)*N+y-1];
	   }
   cout<<endl;
 
  }
 cout<<endl<<"输入n退出,按任意键继续输出可走路线:"<<endl;
  c=getchar(); 
}


void main()
{ cout<<endl;
  cout<<"**********************************马踏棋盘**************************************"<<endl;
  cout<<"                                                                                "<<endl;
 int x,y,way,way0;     
 outroad();
 mixdir();
 cout<<"请输入初始位置:";
 cout<<endl<<"请输入横坐标(1--8)  x=";   //用户的输入过程
 cin>>x;
 cout<<"请输入纵坐标(1--8)  y=";
 cin>>y;
 a[1][0]=x,a[1][1]=y;
 chess[(x-1)*N+y-1]=1; //在chess数组中对相应点赋值，即输出时用到的各点的顺序号  
 while(1){
   if(a[1][2]>=8)break; //出发点的八个方向都已走过，表示所有的方法均已找出 
if(a[step][2]>=8) //此点的八个方向都已走过，应该退回到上一次走的点 
{   
     x=a[step][0];
     y=a[step][1];   
     chess[(x-1)*N+y-1]=0;  //将这一点被走过的痕迹抹去 
    a[step][0]=a[step][1]=a[step][2]=0;
a[step-1][2]++; //将上一次走的点走的方向发生变化 
step--; //步数减一 
    }                
   else    //此点的八个方向未全走过，应走此方向 
  {way0=a[step][2];
   a[step][2]++; //确定下次应走的方向 
   x=a[step][0];
   y=a[step][1];  
   way=dir[x-1][y-1][way0];
   x=a[step][0]+HTryX[way]; 
   y=a[step][1]+HTryY[way]; //确定按这次的方向走应走到的x,y坐标 
   if(x<1||y<1||x>N||y>N||chess[(x-1)*N+y-1]!=0)continue;//此点不满足要求 
  chess[(x-1)*N+y-1]=++step; //走到这一点 
   a[step][0]=x;
   a[step][1]=y;  
   a[step][2]=0;             //标记这一点 
   if(step==N*N){    //步数已满 
     print();  //输出结果 
      if(c=='n')break; 
      chess[(x-1)*N+y-1]=0; a[step][0]=a[step][1]=a[step][2]=0; 
      a[step-1][2]++;
      step--; //退回前一步 
     } 
    } 
} 
 
}