骑士巡游问题
1.想把定义棋盘大小放到主函数里，让用户在黑窗口定义2.想显示出巡游次数
3.想用time()函数计算时间复杂度
#include<iostream>
#include<stdio.h>
using namespace std;
//定义棋盘的大小
#define N 12
#define LOSE 0
#define SUCCEED 1
void printknightgo(); //输出结果
int knightgo(int x,int y); //运算走法
int chessboard[N][N] = { 0 }; //建立棋盘
void main(){
int x,y;
printf("\n");
printf("***************游戏开始!***************\n");
cout<<"请输入坐标"<<endl;
cin>>x>>y; //输入坐标
if(knightgo(x,y)){ //开始运算走法，如果成功则返回成功，否则返回失败
cout<<"成功完成"<<endl;
}
else{
cout<<"失败"<<endl;
}
printknightgo(); //输出结果
}
//输出结果的算法
void printknightgo(){
for(int i = 0;i < N; i++){
for(int j = 0;j < N;j++){
cout<<chessboard[i][j]<<"\t";
}
cout<<endl;
}
}
int knightgo(int x,int y){
chessboard[x][y] = 1;//将第一步标为1
int step;//走的步数
int nextx[8] = {-1,1,-2,2,-2,2,-1,1};//走的X的步法
int nexty[8] = {2,2,1,1,-1,-1,-2,-2};//走的Y的步法
int recordNextx[8]={0};//记住下步可走X的位置，并用count来记数
int recordNexty[8]={0};//记住下步可走Y的位置，并用count来记数
int tempx,tempy;//用于临时记住X和Y
int i,j;//临时计数变量
int count = 0;//记住可循环的个数
int exist[8]={0};//第2次找8个方向每个可走的记录
for(step=2;step <=N*N;step++){//把输进来或循环的位置，找下一个能走的位置,并记住这些位置和可走的个数
for(i = 0;i < 8;i++){ //把上次记录重置0;
recordNextx[i] = 0;
recordNexty[i] = 0;
exist[i] = 0;
}
count = 0;
for(i = 0;i < 8;i++){//第一次循环，找可走的个位置，并记录可走方向的个数
tempx = x + nextx[i];//tempx为临时记录X
tempy = y + nexty[i];//tempy为临时记录Y
if(chessboard[tempx][tempy] == 0 && tempx >= 0 && tempx < N && tempy >= 0 && tempy < N){//当这个位置没走过和不走出盘外时，才能记录
recordNextx[count] = tempx;
recordNexty[count] = tempy;//记录可走方向的x,y坐标
count++; //记录可以走的方向的个数
}
}
//把记住的位置,找他们的下个能走位置的个数,就是重复上面循环，只需记录可走方向的个数
if(count == 0){//如果没有出路则返回失败
return LOSE;
}
else {//如果只有一条路，则走这一条路
if(count == 1){
x = recordNextx[0];//因为可走方向只有一个，所记录中就有recordNext(x,y)[0];
y = recordNexty[0];
chessboard[x][y] = step; //把第几步写入这个棋盘的位置
}
else{//有多条路可以走的话
for(j = 0;j < count;j++){//第一个点记录的可走的方向，并找出们下一个方向可以走的的方向的个数
for(i = 0;i < 8;i++){//找第2个点8个方向可走的方向
tempx = recordNextx[j] + nextx[i];
tempy = recordNexty[j] + nexty[i];
if(chessboard[tempx][tempy] == 0 && tempx >= 0 && tempx < N && tempy >= 0 && tempy < N){//当这个位置没走过和不走出盘外时，才能记录
exist[j]++;//记录第2个点可走方向的个数
}
}
}
//找最方向个数最小的一条路
int min = exist[0];
int last = 0;//用于记住，recordNext(x,y)中可走方向中，能走方向数目最小的一个方向
for(i = 1;i < count;i++){//找出方向数目最小的数和方向
if(exist[i]<min){
min = exist[i];
last = i;
}
}
x = recordNextx[last];//将这个方向给x,y;
y = recordNexty[last];
chessboard[x][y] = step; //将这个步数写出这个棋盘
}
}
}
return SUCCEED;
}
运行结果：***************游戏开始!***************
请输入坐标
2 4
成功完成
97 20 69 24 95 2 59 26 53 4 49 28
70 23 96 21 68 25 54 3 58 27 52 5
19 98 71 102 1 94 67 60 55 50 29 48
72 101 22 93 108 103 86 57 46 61 6 51
99 18 135 112 105 92 107 66 85 56 47 30
136 73 100 109 134 113 104 87 82 45 62 7
17 132 123 138 111 106 91 114 65 84 31 44
74 137 110 133 122 125 116 83 88 81 8 63
131 16 143 124 139 90 119 80 115 64 43 32
144 75 140 121 128 117 126 89 42 35 38 9
15 130 77 142 13 120 79 118 11 40 33 36
76 141 14 129 78 127 12 41 34 37 10 39
Press any key to continue
