文档介绍:贪心算法求解马踏棋盘
#include "" #define X 8
#define Y 8
#define N 8
struct child
{
int x;
int y;
int wayout;//子节点访问次数
}node[N];
int chess[X][Y]; int addx[N]={-2,-1,1,2,2,1,-1,-2};
int addy[N]={1,2,2,1,-1,-2,-2,-1};
int way(int x,int y,int m,int n)//计算子节点出口多少 {
int i;
int tx;
int ty;
int count=-1;
for(i=0;i<N;i++)
{
tx=x+addx[i];
ty=y+addy[i];
if((x>=0)&&(y>=0)&&(x<X)&&(y<Y)&&(tx>=0)&&(ty>=0)&&(tx<X)&&(ty<Y)&&(chess[tx][ty]=
=0)&&(chess[x][y]==0)&&((tx!=m)||(ty!=n)))//进行子节点出口的判定
{
count++;
}
}
return count;
}
int finalway(int x,int y)//完成最后节点的确定 {
chess[x][y]=X*Y-1;
int tx;
int ty;
int i;
for(i=0;i<N;i++)
{
tx=x+addx[i];
ty=y+addy[i];
if((x>=0)&&(y>=0)&&(x<X)&&(y<Y)&&(tx>=0)&&(ty>=0)&&(tx<X)&&(ty<Y)&&(chess[tx][ty]==0)&
&((tx!=x)||(ty!=y)))//进行最后节点出口的判定
{
chess[tx][ty]=X*Y;
return 1;
}
}
return 0;
}
void sort(child *point) {
int i,j;
struct child swap;
for(i=0;i<N;i++)//采用冒泡排序
{
for(j=0;j<N-1;j++)
{
if(point[j].wayout>point[j+1].wayout)
{
s[j];
point[j]=point[j+1];
point[j+1]=swap;
}
}
}
/*for(i=0;i<N;++i)
{
for(t=i,j=i+1;j<N;++j)
if(point[j].wayout<point[t].wayout)
t=j;
if(t>i)
{
s[i];
point[i]=point[t];
point[t]=swap;
}
}*/
}
int TravelChessBoard(int x,int y,int tag)
{
int xx=x;
int yy=y;
int i;
/*if(tag>X*Y)
{
//c