贪心算法求解马踏棋盘
- 格式：doc
- 大小：13.96 KB
- 文档页数：4
#include "stdio.h"
#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
tx=x+addx[i];
ty=y+addy[i];
if((x>=0)&&(y>=0)&&(x
{
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
tx=x+addx[i];
ty=y+addy[i];
if((x>=0)&&(y>=0)&&(x
{
chess[tx][ty]=X*Y;
return 1;
}
}
return 0;
}
void sort(child *point)
{
int i,j;
struct child swap;
for(i=0;i
for(j=0;j
if(point[j].wayout>point[j+1].wayout)
{
swap=point[j];
point[j]=point[j+1];
point[j+1]=swap;
}
}
}
/*for(i=0;i
for(t=i,j=i+1;j
if(t>i)
{
swap=point[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)
{
//chess[xx][yy]=tag;
printf("The horse has travelled the chess borad\n");
return 1;
}*/
if(tag!=X*Y)
{
for(i=0;i
node[i].x=xx+addx[i];
node[i].y=yy+addy[i];
node[i].wayout=way(node[i].x,node[i].y,xx,yy);
}
sort(node);
for(i=0;(node[i].wayout<0)&&(i<=N);i++);//去掉访问过的节点和没有出口的节点
if(i==N)return 0;
for(;i
xx=node[i].x;
yy=node[i].y;
chess[xx][yy]=tag;
if(TravelChessBoard(xx,yy,tag+1)==1)
return 1;
else chess[xx][yy]=0;
}
}
else
{
if(finalway(xx,yy))return 1;
else
{
return 0;
}
}
return 0;
}
int main()
{
int i,j;
for(i=0;i
for(j=0;j
}
//if(TravelChessBoard(4,5,1))
// int m=TravelChessBoard(4,5,1);
//chess[2][0]=1;
TravelChessBoard(2,0,1);
for(i=0;i
for(j=0;j
printf("%d",chess[i][j]);
printf("\t");
}
printf("\n");
}
//else
//printf("The horse cannot travel the chess board\n");
return 1;
}
