题目

在8×8的国际象棋棋盘中，给出马的初始位置，求出马踏遍棋盘每个位置的路线图(棋盘中每个位置只能走一次)

思路

国际象棋中，马走的规则和中国象棋相似，为斜两格行走(即向任意方向走两格，再向与前面行走方向垂直的方向走一格)
每个位置最多可以向八个方向行走，用回溯算法的话，我们会对每个方向进行尝试，走不通则进行回溯，知道可以走通时，输出路线图；我们这里采用贪心算法，在当前位置时，我们对每个方向的位置进行检测，检测他们可以走的方向数量，然后对这些方向数量进行排序；优先向方向数量少的方向走，当遇到当前位置的每个方向都走不通时(即走过的方向数达到上限)我们进行出栈操作，然后回到上一个位置，按照以上方法持续进行，直到走过所有的位置时输出路线图。

代码

#include <stdio.h>
#define ROW 8
#define COL 8
#define MAXSTEP 64typedef struct horse {int x;	//横坐标 int y;	//纵坐标 int dir; //方向 
}Horse;int top; //栈顶 
Horse horse[MAXSTEP];
int chess[ROW+1][COL+1]; //存储期盼对应路线 
int dir[8][2] = {{2,-1},{-2,-1},{-2,1},{2,1},{1,-2},{-1,-2},{-1,2},{1,2}};void Init(); //初始化数据 
void push(int x,int y); //入栈 
void pop();// 出栈
void mark_chess(int x,int y);// 在棋盘上标记路线 
void print_chess();// 打印棋盘上的路线
void run();// 核心(贪心算法)int main()
{int x,y;while(1){printf("请输入马的初始位置 x(1-8) y(1-8)：");scanf("%d %d",&x,&y);if(x<1||x>ROW||y<=0||y>COL){printf("初始数据错误,请重新输入 x(1-8) y(1-8)");} else{break;}		}Init();push(x,y);mark_chess(x,y);run();
}//初始化数据 
void Init()
{for(int i=0;i<MAXSTEP;i++){horse[i].x=0;horse[i].y=0;horse[i].dir=-1;}for(int i=0;i<=ROW;i++){for (int j=0;j<=COL;j++){chess[i][j]=0;}}top=-1;
}
//入栈 
void push(int x,int y)
{horse[++top].x=x;horse[top].y=y;horse[top].dir=-1;} 
// 出栈
void pop()
{horse[top].x=0;horse[top].y=0;horse[top].dir=-1;top--;} // 在棋盘上标记路线 void mark_chess(int x,int y){chess[y][x] = top + 1;}// 打印棋盘上的路线 void print_chess(){printf("马在棋盘上的路线图：\n"); for(int i=1;i<=ROW;i++){for (int j=1;j<=COL;j++){printf("%4d",chess[i][j]);}printf("\n");}}// 核心(贪心算法) void run() {int x_now,y_now;while(1){//所有地方已经过 if(top+1>=MAXSTEP){print_chess(); break;}//当前位置 x_now=horse[top].x;y_now=horse[top].y;//记录对应方向可以走几个方向		int next[ROW]={0};for(int i=0;i<ROW;i++){int x_next=x_now+dir[i][0];int y_next=y_now+dir[i][1];if(x_next>0&&x_next<=COL&&y_next>0&&y_next<=ROW&&chess[y_next][x_next]==0){for(int j=0;j<ROW;j++){int x_next_next=x_next+dir[j][0];int y_next_next=y_next+dir[j][1];if(x_next_next>0&&x_next_next<=COL&&y_next_next>0&&y_next_next<=ROW&&chess[y_next_next][x_next_next]==0){next[i]++;}} }}//对各个方向可以走的方向数进行排序，先走方向数小的方向		int t=ROW+1;int real_next[ROW]={0};int index=0;for(int i=0;i<ROW;i++){t=ROW+1;for(int j=0;j<ROW;j++){if(next[j]<t){real_next[i]=j;t=next[j];			index=j;}}next[index]=ROW+1;}//开始走 int dir_now=0;for(dir_now=horse[top].dir+1;dir_now<ROW;dir_now++){int x_real=x_now+dir[real_next[dir_now]][0];int y_real=y_now+dir[real_next[dir_now]][1];horse[top].dir++;if(x_real>0&&x_real<=COL&&y_real>0&&y_real<=ROW&&chess[y_real][x_real]==0){push(x_real,y_real);mark_chess(x_real,y_real);break;}}//当前位置走过的方向数到达上限，此时此路不通，进行回退(出栈) if(horse[top].dir>=7){chess[horse[top].y][horse[top].x] = 0;pop();}}}