(去豆瓣工作)
(天一生水)
(小马先森)
(玩儿着看世界)
第三方登录：【问题描述】 在一个具有8&8个方格的国际象棋盘上，从棋盘的任何一个方格 开始，让马按照允许的走步规则（L形走法）走遍所有方格，每个方格 至少并且只准走过一次。试设计一个算法实现这个有趣的问题。
【基本要求】 将马随机放在棋盘的某个方格中，根据J.C.Warnsdorff提出的规则 来进行遍历。编制非递归程序，求出马的行走路线，输出所走各步的 位置。
【测试数据】 由用户自行指定一个马的起始位置（i, j）, 0&i, j&7。
【实现提示】 （1）棋盘用 8&8的二维数组表示。 （2）当马位于位置（i, j）时，可以走到下列8个位置之一：(i-2, j+1), (i-1, j+2), (i+1, j+2), (i+2, j+1), (i+2, j-1), (i+1, j-2), (i-1, j-2), (i-2, j-1)。 但是，如果（i,j）靠近棋盘的边缘，上述有些位置可能超出棋盘范围， 成为不允许的位置。8个可能位置的位移量可以用两个一维数组imove[8] 和jmove[8]来存储。
（3）根据J.C.Warnsdorff提出的规则来设计算法。该规则是在所有 可走步的（尚未走过的）方格中，马只能走向这样一个方格：从该方格 出发，马可走步的方格数为最少，如果可走步的方格数相等，则从马的 当前位置来看，方向序号小的优先。 （4）采用Warnsdorff规则在大多数情况下能够实现遍历，但并不能 确保成功。
【选作内容】 （1）按求出的行走路线，将数字1, 2, 3,&,64依次填入一个8&8的方 阵，输出之。 （2）在不考虑Warnsdorff规则的情况下，求出从某一起点出发的多 条以至全部行走路线。
允许我直接贴代码了
1 #include"queue.h"
2 struct point {
int//马的x方向
int//马的y方向
7 typedef struct Queue{
struct point
queue[MaxQueueSize];
int//头指针
int//尾指针
int//设置标记位
14 //初始化队列操作
15 void QueueInitiate(SeqCQueue *Q){
Q-&front=0;
Q-&rear=0;
21 //判断队列是否为空
22 int QueueNotEmpty(SeqCQueue Q){
if(Q.front==Q.rear&&Q.tag==0)
29 //入队操作
QueueAppend(SeqCQueue *Q,point
if(Q-&tag==1&&Q-&front==Q-&rear){
printf("队列已满，无法插入！\n");
Q-&queue[Q-&rear]=x;
Q-&rear=(Q-&rear+1)%MaxQueueS
40 //出队操作
41 void QueuePop(SeqCQueue *Q,point
if(Q-&tag==0&&Q-&front==Q-&rear){
printf("队列已空，无元素可以出队列！\n");
*d=Q-&queue[Q-&front];
Q-&front=(Q-&front+1)%MaxQueueS
51 #include&stdio.h&
52 #include&string.h&
53 #define MaxQueueSize 64
54 #include "queue.h"
55 #define MAXN 8
57 SeqCQueue Q;
59 int m,n;
60 int//记录马走的步数
61 int map[MAXN][MAXN];//8*8的国际象棋棋盘
62 int dir[8][2]={{-2,-1},{-2,1},{-1,-2},{-1,2},{1,-2},{1,2},{2,-1},{2,1}};//马理论上所能走全部的位置
65 //求出该位置的马所能走的步数
66 int _step(int x,int y){
int count=0;
for( i=0;i&8;i++){
xi=x+dir[i][0];
yi=y+dir[i][1];
//边界条件以及!map[xi][yi]表示未走过的位置
if(xi&=0&&xi&=MAXN-1&&yi&=0&&yi&=MAXN-1&&!map[xi][yi])
79 int BFS(point s)
int i,x,y,
QueueInitiate(&Q);//初始化队列
QueueAppend(&Q,s);//入队操作
int flag=0 ;
//当队列非空时，进行广度优先搜索
while(QueueNotEmpty(Q))
QueuePop(&Q,&hd);//出队列
map[hd.x][hd.y]=step++;//标记该位置已走过
printf("%d,%d\n",hd.x,hd.y);//输出走过的位置
int minstep=10;//初始的最小步数
int flag=0;//标记
//8个方向进行搜索
for( i=0;i&8;i++){
x=hd.x+dir[i][0];
y=hd.y+dir[i][1];
x&=MAXN-1&&y&=0&&y&=MAXN-1&&!map[x][y]){
//如果小于当前的最小步数，则让队列元素出队列，并让当前的元素入队列
if(_step(x,y)&minstep){
minstep=_step(x,y) ;
t.x=x,t.y=
if(flag) QueuePop(&Q,&th) ;//如果是第一次的话，就不用出队列了；
QueueAppend(&Q,t) ;
return step-1;
115 int main()
while(scanf("%d%d",&m,&n)!=EOF){
//判断起始位置是否合法
if(m&0||m&7||n&0||n&7){
printf("起始位置不合法！\n\n");
printf("\n");
memset(map,0,sizeof(map));//将8*8的棋盘全部置为0
start.x=m,start.y=n;
step=BFS(start);
//按求出的行走路线，将数字1, 2, 3,&,64依次填入一个8&8的方阵，输出
for(int i=0;i&MAXN;i++){
for(int j=0;j&MAXN;j++){
printf("%-3d",map[i][j]);
printf("\n");
printf("step=%d.\n",step);
printf("\n");
阅读(...) 评论()}