(SIZE-2)*(SIZE-2)棋盘骑士游历问题

来源:百度文库 编辑:神马文学网 时间:2024/03/29 13:38:54

 

16.(SIZE-2)*(SIZE-2)棋盘骑士游历问题

 

/*(SIZE-2)*(SIZE-2)棋盘骑士游历问题*/

 

#include

#include

using namespace std;

 

/*常量定义棋盘大小为(SIZE-2)*(SIZE-2)*/

#define SIZE 9

 

int num1=0;                             //各个位置遍历总数;           

 

/*类go用于实现棋盘的遍历*/

class go{

private:

       int row[8];                            

       int col[8];                          //row,col为下一步位置的八种可能;

       int h[SIZE][SIZE];                   //拓展后棋盘大小;

       int num;                             //一个位置遍历方法总数;

public:

       go(void) {                           //构造函数,实现棋盘初始化等工作; 

              int i,j;

              int r[8]={1,2,2,1,-1,-2,-2,-1};

              int c[8]={-2,-1,1,2,2,1,-1,-2};

              for(int k=0;k<=7;k++){

                     row[k]=r[k];

                     col[k]=c[k];

              }

              num=0;

              for(i=2;i

                     for(j=2;j

                            h[i][j]=0;

                     }

              }

       }

       ~go(void) {}                         //析构函数;    

       void tryit(int a,int b,int c);       //遍历函数; 

       void print();                        //输出函数;

       void setzero();                      //置零函数; 

};

 

/*数字代表走的步数*/

void go::print()

{

       cout<<"结果"<

       for(int i=2;i

              for(int j=2;j

                            cout<

              }

              cout<

       }

       cout<

}

 

/*一个位置开始的全部遍历,递归回溯主体*/

void go::tryit(int a=2,int b=2,int count=1)

{

       int u,v;

       h[a][b]=count;

       count++;

       for(int i=0;i<8;i++){                               //八个方向上的尝试;

                     u=a+row[i];

                     v=b+col[i];

                     if(u>=2&&u=2&&v

                            h[u][v]=count;

                            if(count==(SIZE-4)*(SIZE-4)){           //一种方法结束,输出;

                                   num++;

                                   num1++;

                                   print();

                            }

                            else{                                   //一种方法没完成,回溯;

                                   tryit(u,v,count);                 

                            }

                            h[u][v]=0;                              //完成一种方法后置零;         

                     }

       }

}

 

/*另一个位置开始前的置零工作*/

void go::setzero()

{     int i,j;

       int r[8]={1,2,2,1,-1,-2,-2,-1};

       int c[8]={-2,-1,1,2,2,1,-1,-2};

       num=0;

       for(int k=0;k<=7;k++){

              row[k]=r[k];

              col[k]=c[k];

       }

       for(i=2;i

              for(j=2;j

                     h[i][j]=0;

              }

       }

}

 

 

int main()

{

       go R;

       for(int i=2;i

              for(int j=2;j

                     cout<<"初始位置为("<

                     R.tryit(i,j,1);

                     R.setzero();

              }

       }

       cout<<"遍历总数为:"<

       return 0;

}