#include<iostream.h>
#include<iomanip.h>
#include<stdio.h>
const int N = 8;
int w = 0;
int way1[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int way2[8] = { 1, 2, 2, 1, -1, -2, -2, -1};
int ch[N*N] = { 0 };
int a[N*N+1][3] = { 0 };
int dir[N][N][8];
int st = 1;
char c = 'y';
int weight[N][N];
void caculate();
void dirctions();
void print();
int check(int i, int j);
void caculate() { //计算各点的权值
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 + way1[k];
y = j + way2[k];
if ( x >= 1 && x <= N && y >= 1 && y<=N )
weight[i-1][j-1]++;
}
}
int check(int i,int j) { //检查(i,j)是否在棋盘内
if( i < 1 || i > 8 || j < 1 || j > 8 )
return 0;
return 1;
}
void directions() { //求出各点的最佳方向序列,即优先向权值小的方向
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 + way1[way_1];
y1 = j + way2[way_1];
way_2 = dir[i][j][m];
x2 = i + way1[way_2];
y2 = j + way2[way_2];
n1 = check(x1+1,y1+1);
n2 = check(x2+1,y2+1);
if( ( n1==0 && n2 ) || //k方向不可达到,而m方向可达到
( n1 && n2 && weight[x1][y1] > weight[x2][y2] )//都可达到但m方向权值小
) {
dir[i][j][k] = way_2;
dir[i][j][m] = way_1; //交换两个方向值
}
}
}
}
}
void print() {
int x, y;
cout<<"\n---------"<<++w<<"answer---------\n";
for(x = 1; x < N + 1; x++) {
cout<<endl;
for(y = 1; y < N + 1; y++)
cout<<setw(3)<<ch[(x-1)*N+y-1];
cout<<endl;
}
cout<<"\nPress n to quit ,press any other key to continue.\n";
c = getchar(); //询问是否继续输出结果
}
void main() {
int x, y, way, way0;
caculate();
directions();
cout<<"Please enter the row and column of the starting point.\n";
cin>>a[1][0]>>a[1][1]; //输入行数和列数
getchar(); //接收回车符
x = a[1][0], y = a[1][1];
ch[(x-1)*N+y-1] = 1; //在ch数组中对相应点赋值
while(1) {
if(a[1][2] >= 8) //出发点的八个方向都已走过,表示所有的方法均已找出
break;
if(a[st][2] >= 8) { //此点的八个方向都已走过,应该退回到上一次走的点
x = a[st][0];
y = a[st][1];
ch[(x-1)*N+y-1] = 0; //将这一点被走过的痕迹抹去
a[st][0] = a[st][1] = a[st][2] = 0;
a[st-1][2]++; //使上一次走的点走的方向发生变化
st--; //步数减一
}
else { //此点的八个方向未全走过,应走此方向
way0 = a[st][2];
a[st][2]++; //确定下次应走的方向
x = a[st][0];
y = a[st][1];
way = dir[x-1][y-1][way0];
x = a[st][0] + way1[way];
y = a[st][1] + way2[way]; //确定按这次的方向走应走到的x,y坐标
if(x<1||y<1||x>N||y>N||ch[(x-1)*N+y-1]!=0) //此点不满足要求
continue;
ch[(x-1)*N+y-1] = ++st; //走到这一点
a[st][0] = x;
a[st][1] = y;
a[st][2] = 0; //标记这一步
if(st == N*N) { //步数已满
print(); //输出结果
if(c == 'n')
break;
ch[(x-1)*N+y-1] = 0;
a[st][0] = a[st][1] = a[st][2] = 0;
a[st-1][2]++;
st--; //退回前一步
}
}
}
}
温馨提示:内容为网友见解,仅供参考