本文共 3276 字，大约阅读时间需要 10 分钟。

 

//         骑士旅行之迷宫算法

//程序马骑士旅行路线想像成一个迷宫,利用堆栈存储一条正确路线。//结合游戏玩家的无敌玩法,即打胜了存档,打输了调档,最终自然是只赢不输。//本程序也一样,走对存档,走错了调档,最终自然是会找到正确路线。

#include"iostream.h"

#include"stdio.h"#define STP 55         //骑士旅行步数,一般取50到58步之间,取64步调试时间太长

//定义点变量类形typedef struct{ int x;int y;int z;} NONCE;

//函数原数

int startpd(NONCE [8][8],NONCE);    //起点判断NONCE next(NONCE);     //试探下一步函数void save(NONCE [8][8],NONCE [100],int);  //存档void load(NONCE [8][8],NONCE [100],int);  //读档int bjpd(NONCE);             //边界判断int hfpd(NONCE [8][8],NONCE); //合法点判断

//程序入口

int main(){ NONCE chess[8][8];   //定义棋盘,行列表示格子,成员x表示棋盘步数,成员z表示下一步将要试探的地方                     //由于骑士最多只能走八个方向,故z值只能取 0 ~ 7   int i,j,k;NONCE start;   for(i=0;i<8;i++)     for(j=0;j<8;j++)      {  start.x=i;start.y=j;start.z=0; if(startpd(chess,start))goto endfor;    //起点判断,如果该点可以为起点则返回1                                                //否则返回0      }endfor:   //输出    for(i=0;i<8;i++)     {        for(j=0;j<8;j++)  {     if(chess[i][j].x==-1)         //骑士没有走的地方显示 "@"     cout << "@    ";    else     printf("%2d   ",chess[i][j].x);  //骑士走过的地方显示所走的是第几步  }      cout << endl << endl;     }return 0;} //end main

//起点判断,如果该点可以为起点则返回1//否则返回0int startpd(NONCE chess[8][8],NONCE start){ NONCE  stack[100];  //定义堆栈 NONCE  nexttmp;int point;int i,j,k;

//将棋盘清空

    for(i=0;i<8;i++)      for(j=0;j<8;j++)       {  chess[i][j].x=-1; chess[i][j].y=0; chess[i][j].z=0;       }

//将堆栈清空

    for(i=0;i<100;i++)      {        stack[i].x=0;       stack[i].y=0;       stack[i].z=0;      }

//将起点赋值给栈底

  point=0;    stack[point].x=start.x;    stack[point].y=start.y;    stack[point].z=start.z;

  do{     nexttmp=next(stack[point]);   //试探下一步      if(hfpd(chess,nexttmp))     //判断试探的下一步是否合法  {     point++;               //如果合法,则存档      stack[point]=nexttmp;    save(chess,stack,point);  //存档  }      else if(stack[point].z<7)   //如果不合法,则判断8种走法是否走完   {                        //如果没走完,则继续试探下一种走法      stack[point].z++;  }      else  {     point--;               //如果8种走法都走完还是没有出路,则已表示该点                                  //为死点,退回到上一步继续试探,即像游戏玩家那调档    load(chess,stack,point);  //读档    stack[point].z++;  }

       if(stack[0].z>=8)return 0;   //如果栈底的8种走都已走完,则表示该点不能作为起点,函数返回0

       cout << "  " << point << endl;    }while(point<=STP);             //如果已走完指定的步数,退出试探,函数返回1return 1;}  //end startpd

//存档函数

void save(NONCE chess[8][8],NONCE  stack[100],int point){ int i,j,k;

  for(i=0;i<8;i++)for(j=0;j<8;j++){chess[i][j].x=-1;chess[i][j].y=0;chess[i][j].z=0;}

  for(k=0;k<=point;k++)    {       chess[stack[k].x][stack[k].y].x=k;      chess[stack[k].x][stack[k].y].y=0;      chess[stack[k].x][stack[k].y].z=stack[k].z;    }}  //end save

//读档函数

void load(NONCE chess[8][8],NONCE stack[100],int point){ int i,j,k;  for(i=0;i<8;i++)for(j=0;j<8;j++){chess[i][j].x=-1;chess[i][j].y=0;chess[i][j].z=0;}  for(k=0;k<=point;k++)    {       chess[stack[k].x][stack[k].y].x=k;      chess[stack[k].x][stack[k].y].y=0;      chess[stack[k].x][stack[k].y].z=stack[k].z;    }}//end load

//试探下一步点函数

NONCE  next(NONCE  non){ NONCE  nex;begin: if(non.z==0)   {    nex.x=non.x+2;   nex.y=non.y-1;   } else if(non.z==1)   {    nex.x=non.x+1;   nex.y=non.y-2;   } else if(non.z==2)   {    nex.x=non.x-1;   nex.y=non.y-2;   } else if(non.z==3)   {    nex.x=non.x-2;   nex.y=non.y-1;   } else if(non.z==4)   {    nex.x=non.x-2;   nex.y=non.y+1;   } else if(non.z==5)   {    nex.x=non.x-1;   nex.y=non.y+2;   } else if(non.z==6)   {    nex.x=non.x+1;   nex.y=non.y+2;   } else if(non.z==7)   {    nex.x=non.x+2;   nex.y=non.y+1;   } nex.z=0; if(bjpd(nex))  {     non.z++;    goto begin;  }return nex;} // end   nextpd

//边界判断函数int bjpd(NONCE nex){ if(nex.x<0||nex.x>7||nex.y<0||nex.y>7)    return 1;else    return 0;}//end bjpd

//合法点判断函数

int hfpd(NONCE chess[8][8],NONCE non){ if(chess[non.x][non.y].x==-1)   return 1;else   return 0;} // end nextpd