aipeng.txt

马踏棋盘 问题的解法

#include
#include
#include
int map[12][12];//定义为12*12的棋盘
int status[12][12];//定义每个点的状态
int kp;
int c[8][2]={{2,1},{2,-1},{1,2},{1,-2},
{-2,1},{-2,-1},{-1,2},{-1,-2}};//可转移的方向
/*//////////////////////////////////////////////*/
void PrintMap(int a[12][12])  /* 打印棋盘状态 */
{int i,j,i2,j2;
 printf(\n);
 for (i=2;i<=9;i++)
  { for (j=2;j<=9;j++)  printf(%3d,a[i][j]);
    printf(\n);
  }
 }
/*———————————————————————*/
void status2(void)  /* 计算棋盘各点条件数 */
{ int i,j,k,i2,j2,kz;
  for(i=0;i<12;i++)
    for(j=0;j<12;j++)
      status[i][j]=100;
  for(i=2;i<=9;i++)
    for(j=2;j<=9;j++)
     {kz=0;
      for (k=0;k<=7;k++)
       {i2=i+c[k][0];j2=j+c[k][1];//移动试探
         if (map[i2][j2]<50)  kz++;
        }
      status[i][j]=kz;//每个点的可移动总数
     }
 cout<<打印每个点的可移动总数表<  PrintMap(status);//打印每个点的可移动总数表
  cout<<______________________________________< 

 }
/*——————————————————————*/
void sort1(int b1[],int b2[])  /* 对8个可能的方向按条件数排序 */

{int i,j,mini,t; /*b1[]记录状态值（升序），b2[]记录排序后的下标 */
 for (i=0;i<7;i++)
  {mini=i;
   for (j=i+1;j<=7;j++)
     if (b1[j]   t=b1[i];b1[i]=b1[mini];b1[mini]=t;
   t=b2[i];b2[i]=b2[mini];b2[mini]=t;
  }
 }
/*——————————————————————*/
void Init(void)  /* 初始化 */
{int i,j,k;
 for(i=0;i<12;i++)
   for(j=0;j<12;j++)
      map[i][j]=100;
 for(i=2;i<=9;i++)
   for(j=2;j<=9;j++)
      map[i][j]=0;
   cout<<正在初始化系统，请稍等.....<   for(int couter=0;couter<=100000000;couter++);
    cout<<初始化完成!< status2();
}
/*——————————————————————*/
void search(int i2,int j2) /* 利用递归回溯进行搜索 */
 {int b1[8],b2[8],i,i3,j3;
  kp++;
   if(kp==65)//如果全部遍历完的输出
   {PrintMap(map);
   exit(0);
  }
  for(i=0;i<=7;i++)
   {b2[i]=i;
    b1[i]=status[i2+c[i][0]][j2+c[i][1]];
    }
  sort1(b1,b2);
  for(i=0;i<=7;i++)
    {i3=i2+c[b2[i]][0]; j3=j2+c[b2[i]][1];
     if (map[i3][j3]==0)
       { map[i3][j3]=kp;  search(i3,j3); map[i3][j3]=0;}
     }
  kp--;
 }
/*————————————————————————*/
//主程序
void main()
{
 int p,q;
 Init();
 cout<<请输入起点(如(2,3)):< cin>>p>>q;
 map[p+1][q+1]=1; kp=1;
 cout<<正在利用递归回溯进行搜索......< search(p+1,q+1);
 cout<<搜索完成.....打印结构、结果:<}