16.(SIZE-2)*(SIZE-2)棋盘骑士游历问题
/*(SIZE-2)*(SIZE-2)棋盘骑士游历问题*/
#include<iostream>
#include<iomanip>
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<SIZE-2;i++){
for(j=2;j<SIZE-2;j++){
h[i][j]=0;
}
}
}
~go(void) {} //析构函数;
void tryit(int a,int b,int c); //遍历函数;
void print(); //输出函数;
void setzero(); //置零函数;
};
/*数字代表走的步数*/
void go::print()
{
cout<<"结果"<<num<<":"<<endl;
for(int i=2;i<SIZE-2;i++){
for(int j=2;j<SIZE-2;j++){
cout<<setw(6)<<h[i][j];
}
cout<<endl;
}
cout<<endl<<endl<<endl;
}
/*一个位置开始的全部遍历,递归回溯主体*/
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<SIZE-2&&v>=2&&v<SIZE-2&&h[u][v]==0){
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<SIZE-2;i++){
for(j=2;j<SIZE-2;j++){
h[i][j]=0;
}
}
}
int main()
{
go R;
for(int i=2;i<SIZE-2;i++){
for(int j=2;j<SIZE-2;j++){
cout<<"初始位置为("<<i<<","<<j<<"),方法如下:"<<endl;
R.tryit(i,j,1);
R.setzero();
}
}
cout<<"遍历总数为:"<<num1<<endl;
return 0;
联系客服