题目
在8×8的国际象棋棋盘中,给出马的初始位置,求出马踏遍棋盘每个位置的路线图(棋盘中每个位置只能走一次)
思路
国际象棋中,马走的规则和中国象棋相似,为斜两格行走(即向任意方向走两格,再向与前面行走方向垂直的方向走一格)
每个位置最多可以向八个方向行走,用回溯算法的话,我们会对每个方向进行尝试,走不通则进行回溯,知道可以走通时,输出路线图;我们这里采用贪心算法,在当前位置时,我们对每个方向的位置进行检测,检测他们可以走的方向数量,然后对这些方向数量进行排序;优先向方向数量少的方向走,当遇到当前位置的每个方向都走不通时(即走过的方向数达到上限)我们进行出栈操作,然后回到上一个位置,按照以上方法持续进行,直到走过所有的位置时输出路线图。
代码
#include <stdio.h>
#define ROW 8
#define COL 8
#define MAXSTEP 64
typedef 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();
}
}
}