一道C语言棋盘最优路径的题目，求教

这题还是有点意思的。

创新互联公司致力于成都网站制作、网站建设,成都网站设计,集团网站建设等服务标准化，推过标准化降低中小企业的建站的成本，并持续提升建站的定制化服务水平进行质量交付，让企业网站从市场竞争中脱颖而出。 选择创新互联公司，就选择了安全、稳定、美观的网站建设服务！

正如diordna所说，因为涉及到全局最优，

大小又是1000x1000，感觉广搜有点困难，所以打算试试DP。。

思路如下，不知道对不对。。

Part.1

设map[i][j]保存棋盘格子的价值 (i = 0..n-1, j = 0..m-1)

设f[i][j][k]记录棋盘(i, j)位置的最大价值和 (i = 0..n-1, j = 0..m-1, k = 0,1,2)

k表示这个位置是怎么来的：

k = 0: 左→右

k = 1: 上→下

k = 2: 下→上

首先初始化 f[i][j][k] = -inf

然后根据题意有：f[0][0][k] = map[0][0], k = 0,1,2

Part.2

又因为不能向左走，实际上就是说第j = 0列的格子只能向下走

所以可以先把f[i][0][1]算出来

f[i][0][1] = max(k=0,1){f[i-1][0][k]} + map[0][j] = f[i-1][0][1] + map[i][0], i = 1..n-1

Part.3

然后考虑任意一个非第0列的格子(i, j), i = 0..n-1, j = 1..m-1

便于思考特殊化一下，假设考虑第j = 1列（当然其它列也一样），

任意一个格子有3种到达方式，分别对应k = 0, 1, 2

但此时我们只知道每个格子的左边格子里的f值

那么我们先计算k=0时刻各格子的f值 (左→右)

f[i][j][0] = max(k=0,1,2){f[i][j-1][k]} + map[i][j], i = 0..n-1, j = 1

Part.4

这样一来各个格子从左边来到后的总价值f就得到了

接下来处理从上到下和从下到上的情况

由于从某个格子开始一旦选择从上到下或从下到上走后就无法回头了

不妨从上到下开始：

f[i][j][1] = max(k=0,1){f[i-1][j][k]} + map[i][j], i = 1..n-1, j = 1

然后从下到上：

f[i][j][2] = max(k=0,2){f[i+1][j][k]} + map[i][j], i = n-2..0, j = 1

Part.5

这样一来每个格子对应的3种走法的价值最大值就能得到了

如此回到Part.3循环列j = 1..m-1

最后只要取max(k=0,1){f[n-1][m-1][k]} 即可得到最优路径价值和

试着写了一下，不知道能不能过。。

注意由于开了1000x1000的long数组，所以VC调试的时候注意把堆栈开大一点

#include iostream

using namespace std;

#define MAXN 1000

#define INF 0x7fffffff

long map[MAXN][MAXN];

long f[MAXN][MAXN][3];

long getmax(long a, long b){ return (a  b) ? a : b;}

void init()

{

for(int i = 0; i  MAXN; i++)

{

for(int j = 0; j  MAXN; j++)

{

map[i][j] = -INF;

f[i][j][0] = -INF;

f[i][j][1] = -INF;

f[i][j][2] = -INF;

}

}

}

int main()

{

// Part.1

int n, m;

cin  n  m;

init();

for(int i=0; in; i++)

{

for(int j=0; jm; j++)

{

cin  map[i][j];

}

}

f[0][0][0] = f[0][0][1] = f[0][0][2] = map[0][0];

// Part.2

for(int i=1; in; i++)

{

f[i][0][1] = f[i-1][0][1] + map[i][0];

}

for(int j=1; jm; j++)

{

// Part.3

for(int i=0; in; i++)

{

long max = getmax(getmax(f[i][j-1][0], f[i][j-1][1]), f[i][j-1][2]);

if(max == -INF) continue;

f[i][j][0] = max + map[i][j];

}

// Part.4

for(int i=1; in; i++)

{

long max = getmax(f[i-1][j][0], f[i-1][j][1]);

if(max == -INF) continue;

f[i][j][1] = max + map[i][j];

}

for(int i=n-2; i=0; i--)

{

long max = getmax(f[i+1][j][0], f[i+1][j][2]);

if(max == -INF) continue;

f[i][j][2] = max + map[i][j];

}

}

cout  getmax(f[n-1][m-1][0], f[n-1][m-1][1])  endl;

return 0;

}

C语言。设有下图所示的一个棋盘，在棋盘上的A点，有一个中国象棋的马，并约定马走的规则,从A点跳至B点。

#includestdio.h

//棋盘尺寸

#define X 4

#define Y 8

//B点坐标

#define BX 0

#define BY 8

int pos[100];

int idx = 0;

int drt[4][2]={{2,1},{1,2},{-1,2},{-2,1}};

bool expand(int x,int y ) 

{

int i,xn,yn;

if (x==BX  y==BY)

return true;

if (x0||y0||xX||yY)

return false;

for(i=0;i4;i++)

{

xn=x+drt[i][0];

yn=y+drt[i][1];

pos[2*idx]=xn;

pos[2*idx+1]=yn;

idx++;

if (expand(xn,yn))

return true;

else

idx--;

}

return false;

}

int main( ) {

int x,y,i,j;

int ary[X+1][Y+1];

printf("请输入起始点(x,y)\n");

scanf("%d,%d",x,y);

pos[0]=x;

pos[1]=y;

idx=1;

if(expand(x,y))

{

for(i=0;i=X;i++)

for(j=0;j=Y;j++)

ary[i][j]=0;

for(i=0;iidx;i++)

ary[pos[2*i]][pos[2*i+1]]=i+1;

for(i=0;i=X;i++)

{

for(j=0;j=Y;j++)

printf("%d ",ary[i][j]);

printf("\n");

}

printf("共计%d步\n",idx);

}

else

{

printf("不能从A到达B\n");

}

}

[image]100 棋盘覆盖问题，求c语言数组递归的解答，和思路

棋盘覆盖问题

问题描述：在一个2k×2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。

代码：#includestdio.h

int tile=0;//整型变量，记录L型骨牌的数量  int Matrix[100][100];//定义数据结构

void ChessBoard(int tr,int tc,int dr,int dc,int size)

{//tr和tc分别是棋盘左上角方格的行号、列号；dr和dc分别是特殊方格的行号、列号   if(size==1)  return;  int t=tile++;//L型骨牌号，初值为0   int s=size/2;//分割棋盘

if(drtr+sdctc+s)//用L型骨牌号覆盖左上角子棋盘  ChessBoard(tr,tc,dr,dc,s);// 特殊方格在此棋盘中  else

{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖右下角   Matrix[tr+s-1][tc+s-1]=t; // 覆盖本子棋盘中的其余方格   ChessBoard(tr,tc,tr+s-1,tc+s-1,s);  }

if(drtr+sdc=tc+s)//用L型骨牌号覆盖右上角子棋盘  ChessBoard(tr,tc,dr,dc,s);// 特殊方格在此棋盘中  else

{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖左下角   Matrix[tr+s-1][tc+s]=t;// 覆盖本子棋盘中的其余方格   ChessBoard(tr,tc+s,tr+s-1,tc+s,s);  }

if(dr=tr+sdctc+s)//用L型骨牌号覆盖左下角子棋盘  ChessBoard(tr+s,tc,dr,dc,s);// 特殊方格在此棋盘中  else

{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖右上角   Matrix[tr+s][tc+s-1]=t;// 覆盖本子棋盘中的其余方格   ChessBoard(tr+s,tc,tr+s,tc+s-1,s);  }

if(dr=tr+sdc=tc+s)//用L型骨牌号覆盖右上角子棋盘  ChessBoard(tr+s,tc+s,dr,dc,s);// 特殊方格在此棋盘中  else

{//特殊方格不在此棋盘中用 ,t号L型骨牌覆盖左上角   Matrix[tr+s][tc+s]=t;// 覆盖本子棋盘中的其余方格   ChessBoard(tr+s,tc+s,tr+s,tc+s,s);  }

}

int main()  {   int size,r,c,row,col;          //memset(Matrix,0,sizeof(Matrix));         for(int i=0;i=100;i++)//初始化 为零          {          for(int j=0;j=100;j++)          {           Matrix[i][j]=0;          }         }          scanf("%d",size);//输入棋盘大小           scanf("%d%d",row,col);//输入特殊方格位置          ChessBoard(0,0,row,col,size);          for (r = 0; r size; r++)//输出棋盘覆盖结果          {              for (c = 0; c size; c++)             {                  printf("%2d ",Matrix[r][c]);             }              printf("\n");         }          return 0;  }

输出结果：

骑士游历C语言递归，请大家帮忙看下哪里错了，谢谢

简单的帮你改了一下。

首先是你的程序里面的几个毛病。

chessbord[x][y] = 1;//初始位置 置为1

flag = KnightTrav(1, x, y, chessbord);

if (flag)

中间那一行，因为在函数KnightTrav里面，是先把i的值赋给盘面然后再i+1，而你之前已经把初始位置赋值了1，所以会造成如下后果：

1.盘面上有两个1（这还算好的，但是第二种情况把这种都否定了）

2.由于有了两个1，程序算到最后，算到了i=N*N-1的时候，盘面上再没有任何位置可以赋值，因此程序不管怎样算都不对。

然后还有一个我觉得做得不够好的地方。对于我们程序人员来说，知道数组是从0开始的，但是对于用户来说，想要输入第一行，都得输入0，第二行就输入1，不是很奇怪吗?所以我建议把所有的关于数组大小的数字都加上1，比如chessborad[N][N]变成chessborad[N+1][N+1]

然后就是，你的这个程序效率是很低的，所以在棋盘有64个子的情况下，想要算出来是很要等一等的。建议你把N改成5，或者更低，进行试验判断你的代码对不对。

修改后代码如下，测试运行通过，但是N的值大了极难算出来

#include stdio.h

#define N 6//棋盘大小

int KnightTrav(int i, int x, int y, int chessbord[N+1][N+1]);//把数组增大

//8种方向

static int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};

static int dy[8] = { 1, 2, 2, 1, -1, -2, -2, -1};

main()

{

int i, j, flag, x, y;

static int chessbord[N+1][N+1] ={0};

printf("Input the initial position x,y:");

scanf("%d,%d", x, y);

chessbord[x][y] = 1;//初始位置 置为1

flag = KnightTrav(2, x, y, chessbord); //把1改成2

if (flag)

{//通路则矩阵装输出

printf("Output:\n");

for (i=1; iN+1; i++) //输出的时候就别输出是0的那一行了

{

for (j=1; jN+1; j++)

{

printf("%4d", chessbord[i][j]);

}

printf("\n");

}

}

else

{

printf("No solution!\n");

}

}

int KnightTrav(int i, int x, int y, int chessbord[N+1][N+1])

{//递归函数

int xx, yy, flag, count = -1;

do{

count++;

flag = 0;

xx = x + dx[count];

yy = y + dy[count];

if ((xx=1 xxN+1) (yy=1 yyN+1) chessbord[xx][yy]==0)

{

chessbord[xx][yy] = i;

if (i N*N)

{

flag = KnightTrav(i+1, xx, yy, chessbord);

if (!flag) chessbord[xx][yy] = 0;

}

else

{

flag = 1;

}

}

}while (!flag count8);

return flag;

}

选楼上的吧，他说的count应该小于7是对的。我用do.while比较少，没有注意到，我开始还以为是程序效率问题，所以导致半天算不出来，现在想来，是因为count[8]不知道是几，内存都不知道加到哪里去了。改成7应该就是对的，你可以自己去测试。

PS一个无关的话题，要说最热心的版块我觉得是烦恼-恋爱。在那里问问题五分钟后一刷新回答能有20多个。我经常闲来无事去逛逛，有的人问的问题真的很搞笑。

你还是没有理解这个程序怎么运行的。

你的程序时逐一尝试，只有当前面几种方法都找不到可以落脚的地方的时候，才会使用到不正确的count[8]；

所以，并不是一定就错了，而是有了不确定的因素，有错误的可能性（也就是在count[7]之前就搞定了计算，没有遇到过错误的count[8]），但是你换个位置试，如果有一个地方需要回溯，就会使用到count[8]因此就导致了错误

求数据结构课程设计 马踏棋盘 C语言

没看见你说的是非递归的。

其实我也不懂，碰巧知道答案，在51CTO上下的。 不能插图。

9.3 马踏棋盘（1）

【题目要求】

国际象棋的棋盘为8*8的方格棋盘。现将"马"放在任意指定的方格中，按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次，最终使得"马"走遍棋盘的64个方格。编写一个C程序，实现马踏棋盘操作，要求用1～64这64个数字标注马移动的路径，也就是按照求出的行走路线，将数字1，2，……64依次填入棋盘的方格中，并输出。

国际象棋中，"马"的移动规则如图9-4所示。

图9-4 "马"的移动规则

如图9-4所示，图中实心的圆圈代表"马"的位置，它下一步可移动到图中空心圆圈标注的8个位置上，该规则叫做"马走日"。但是如果"马"位于棋盘的边界附近，它下一步可移动到的位置就不一定有8个了，因为要保证"马"每一步都走在棋盘中。

【题目分析】

马踏棋盘的问题其实就是要将1，2，…，64填入到一个8*8的矩阵中，要求相邻的两个数按照"马"的移动规则放置在矩阵中。例如数字a放置在矩阵的(i,j)位置上，数字a+1只能放置在矩阵的(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)之中的一个位置上。将矩阵填满并输出。这样在矩阵中从1，2…遍历到64，就得到了马踏棋盘的行走路线。因此本题的最终目的是输出一个8*8的矩阵，在该矩阵中填有1，2…64这64个数字，相邻数字之间遵照"马走日"的规则。

解决马踏棋盘问题的一种比较容易理解的方法是应用递归的深度优先搜索的思想。因为"马"每走一步都是盲目的，它并不能判断当前的走步一定正确，而只能保证当前这步是可走的。"马"走的每一步棋都是从它当前位置出发，向下一步的8个位置中的1个行走（在它下一步有8个位置可走的情况下）。因此"马"当前所走的路径并不一定正确，因为它可能还有剩下的可选路径没有尝试，如图9-5所示。

图9-5 "马"的可选路径

如图9-5所示，假设最开始"马"位于棋盘的(0,0)的位置，接下来"马"有两处位置可走，即(1,2)和(2,1)。这时"马"是无法确定走2的位置最终是正确的，还是走3的位置最终是正确的。因此"马"只能任意先从一个路径走下去（例如从2的位置）。如果这条路是正确的，那当然是幸运的，如果不正确，则"马"要退回到第一步，继续从3的位置走下去。以后"马"走的每一步行走都遵循这个规则。这个过程就是一种深度搜索的过程，同时也是一种具有重复性操作的递归过程。可以用一棵"探索树"来描述该深度优先搜索过程，如图9-6所示。

图9-6 深度优先搜索过程

"马"的行走过程实际上就是一个深度探索的过程。如图9-6所示，"探索树"的根结点为"马"在棋盘中的初始位置（这里用4*4的棋盘示意）。接下来"马"有两种行走方式，于是根结点派生出两个分支。而再往下一步行走，根结点的两个孩子又能够分别派生出其他不同的"行走路线"分支，如此派生下去，就得到了"马"的所有可能的走步状态。可以想见，该探索树的叶子结点只可能有两种状态：一是该结点不能再派生出其他的"走步"分支了，也就是"马"走不通了；二是棋盘中的每个方格都被走到，即"马"踏遍棋盘。于是从该探索树的根结点到第二种情况的叶结点构成的路径就是马踏棋盘的行走过程。

如何才能通过搜索这棵探索树找到这条马踏棋盘的行走路径呢？可以采用深度优先搜索的方法以先序的方式访问树中的各个结点，直到访问到叶结点。如果叶结点是第二种情况的叶结点，则搜索过程可以结束，因为找到了马踏棋盘的行走路径；如果叶结点为第一种情况的叶结点，即走不通了，则需要返回到上一层的结点，顺着该结点的下一条分支继续进行深度优先搜索下去。

因此在设计"马踏棋盘"的算法时可以借鉴前面讲过的图的深度优先遍历算法和二叉树的先序遍历算法。但是在这里并不需要真正地构建这样一棵探索树，我们只需要借用探索树的思想。在实际的操作过程中，所谓的探索树实际就是深度优先搜索的探索路径，每个结点实际就是当前的棋盘状态，而所谓的叶结点要么就是在当前棋盘状态下，"马"无法再进行下一步行走；要么就是马踏棋盘成功。该算法描述可如下：

int TravelChess Board (int x,int y,int tag)

{

chess[x][y] = tag;

if(tag == 64) { return 1;}

找到"马"的下一个行走坐标（x1,y1），如果找到返回flag=1,否则返回flag=0；

while(flag ){

if(TravelChessBoard (x1,y1,tag+1))return 1; /*递归调用TravelChess ， 从x1,y1向下搜索；如果从 x1,y1往下马踏棋盘成功，返回1*/

else

继续找到"马"的下一个行走坐标（x1,y1），如果找到返回flag=1,否则返回flag=0；

}

if(flag == 0)

chess[x][y] = 0;

return 0;

}

9.3 马踏棋盘（2）

2010-03-17 08:57 杨峰 清华大学出版社 我要评论(0)

摘要：《妙趣横生的算法（C语言实现）》第9章综合题，，本章将列举一些经典的综合题编程实例。这些题目生动有趣，同时具有一定的难度，因此作者尽量做到讲解深入浅出，把问题讲透彻，讲清楚。同时希望读者能从中得到启发，启迪思维，提高自身的编程水平。本节为大家介绍马踏棋盘。

标签：妙趣横生 C语言实现 妙趣横生的算法（C语言实现）

Oracle帮您准确洞察各个物流环节

9.3 马踏棋盘（2）

该算法中通过函数TravelChess()递归地搜索"马"的每一种走法。其中参数x，y指定 "马" 当前走到棋盘中的位置，tag是标记变量，每走一个棋盘方格，tag自动增1，它标识着马踏棋盘的行走路线。

算法首先将当前"马"处在棋盘中的位置上添加标记tag，然后判断tag是否等于64，如果等于64，说明这是马踏棋盘的最后一步，因此搜索成功，程序应当结束，返回1。否则，找到"马"下一步可以走到的位置(x1,y1)，如果找到这个位置坐标，flag置1，否则flag置0。

下面在flag为1的条件下（即找到x1,y1），递归地调用函数TravelChess()。也就是从x1,y1指定的棋盘中的位置继续向下深度搜索。如果从x1,y1向下搜索成功，即程序一直执行下去，直到tag等于64返回1，那就说明"马"已经踏遍棋盘（马踏棋盘的过程是：先走到棋盘的(x,y）位置，再从(x1,y1)向下深度搜索，走遍全棋盘），于是搜索结束，返回1；否则继续找到"马"的下一个可以行走的坐标(x1,y1)，如果找到这个位置坐标，flag置1，并从(x1,y1)向下重复上述的递归搜索，否则flag置0，本次递归结束。

如果找遍当前位置(x,y)的下一个坐标(x1,y1)（一般情况是8种），但是从(x1,y1)向下继续深度优先搜索都不能成功地"马踏棋盘"（此时flag等于0），则表明当前所处的状态并不处于马踏棋盘的"行走路径"上，也就是说"马"本不应该走到(x,y)的位置上，因此将chess[x][y]置0，表明棋盘中该位置未被走过（擦掉足迹），同时返回0，程序退到上一层的探索状态。

这里应当知道，所谓当前位置(x,y)的下一个坐标(x1,y1)是指"马"下一步可以走到的地方，用坐标(x1,y1)返回。在探索树中它处在(x,y)所在的结点的子结点中，如图9-7所示。

图9-7 (x,y)的下一个坐标(x1,y1)

当前位置(x,y)的下一个坐标(x1,y1)的可选个数由当前棋盘的局面决定。一般情况下是有8种可走的位置（如图9-7所示），但是如果"马"位于棋盘的边缘（如图9-7所示的探索树的根结点）或者8个可选位置中有的已被"马"前面的足迹所占据，在这两种情况下(x1,y1)的可选个数就不是8个了。

上述搜索算法相当于先序遍历探索树，只不过它不一定是将探索树完整地遍历，而是当tag等于64时，也就是棋盘被全部"踏遍"时就停止继续搜索了。

下面给出完整的程序清单供读者参考。

程序清单9-3

/*--------------------------------- 9-3.c --------------------------*/

#include "stdio.h"

#define X 8

#define Y 8

int chess[X][Y];

int nextxy(int *x,int *y,int count) /*找到基于x、y位置的下一个可走的位置*/

{

switch(count)

{

case 0: if(*x+2=X-1 *y-1=0 chess[*x+2][*y-1]==0) {*x =*x+2;*y = *y-1;return 1; } break;

case 1: if(*x+2=X-1 *y+1=Y-1 chess[*x+2][*y+1]==0) {*x = *x+2; *y = *y+1 ;

return 1;}break;

case 2: if(*x+1=X-1 *y-2=0 chess[*x+1][*y-2]==0) {*x = *x+1; *y = *y-2; return 1;} break;

case 3: if(*x+1=X-1 *y+2=Y-1 chess[*x+1][*y+2]==0) {*x = *x+1; *y = *y+2;

return 1;}break;

case 4: if(*x-2=0 *y-1=0 chess[*x-2][*y-1]==0) {*x = *x-2; *y = *y-1; return 1;} break;

case 5: if(*x-2=0 *y+1=Y-1 chess[*x-2][*y+1]==0){*x = *x-2; *y = *y+1; return 1;} break;

case 6:if(*x-1=0 *y-2=0 chess[*x-1][*y-2]==0) {*x = *x-1; *y = *y-2;return 1;}break;

case 7: if(*x-1=0 *y+2=Y-1 chess[*x-1][*y+2]==0) {*x = *x-1; *y = *y+2;

return 1;}break;

default: break ;

}

return 0;

}

int TravelChessBoard(int x,int y,int tag) /*深度优先搜索地"马踏棋盘"*/

{

int xx1 = x, yy1 = y, flag = 0,a,b ,count = 0 ;

chess[x][y] = tag;

if(tag == X*Y) { return 1;}

flag = nextxy(x1,y1,count);

while(flag == 0 count 7){

countcount = count + 1;

flag = nextxy(x1,y1,count);

}

while(flag ){

if(TravelChessBoard(x1,y1,tag+1))return 1;

xx1 = x;yy1 = y;

countcount = count +1;

flag = nextxy(x1,y1,count); /*寻找下一个(x,y)*/

while(flag == 0 count 7){ /*循环地寻找下一个(x,y)*/

countcount = count + 1;

flag = nextxy(x1,y1,count);

}

}

if(flag == 0)

chess[x][y] = 0;

return 0;

}

main()

{

int i,j;

for(i=0;iX;i++)

for(j=0;jY;j++)

chess[i][j] = 0;

if(TravelChessBoard(2,0,1)) {

for(i=0;iX;i++) {

for(j=0;jY;j++)

printf("%d ",chess[i][j]);

printf("\n");

}

printf("The horse has travelled the chess borad\n");

}

else

printf("The horse cannot travel the chess board\n");

getche();

}

9.3 马踏棋盘（3）

2010-03-17 08:57 杨峰 清华大学出版社 我要评论(0)

摘要：《妙趣横生的算法（C语言实现）》第9章综合题，，本章将列举一些经典的综合题编程实例。这些题目生动有趣，同时具有一定的难度，因此作者尽量做到讲解深入浅出，把问题讲透彻，讲清楚。同时希望读者能从中得到启发，启迪思维，提高自身的编程水平。本节为大家介绍int nextxy(int *x,int *y,int count)。

标签：妙趣横生 C语言实现 妙趣横生的算法（C语言实现）

Oracle帮您准确洞察各个物流环节

9.3 马踏棋盘（3）

【程序说明】

本程序中应用二维数组chess[8][8]作为8*8的棋盘，"马"每走到棋盘的(i,j)处，就将当前的步数tag赋值给chess[i][j]。为了方便起见，将数组chess设置为外部变量。另外定义字符常量X，Y，它规定棋盘的大小。本程序清单中将X和Y都设置为8。

函数TravelChessBoard()是上述马踏棋盘算法的具体实现。本程序中初始的(x,y)位置为(2,0)，说明"马"从chess[8][8]的chess[2][0]位置开始进行"马踏棋盘"的。在函数TravelChessBoard()中要调用函数nextxy()。

int nextxy(int *x,int *y,int count)

函数nextxy()包含3个参数：x和y为传递下来的"马"当前踏到棋盘上的位置，它是指针变量。变量count的作用是标记调用nextxy()过程的次数，根据count值的不同，返回基于(x,y)的下一个不同的坐标，以此来避免返回同一个坐标，真正实现寻找"针对当前位置(x,y)的下一个位置"的目的。函数nextxy()的作用是找到"马"当前的位置(x,y)的下一个可以行走的位置，并通过指针修改x、y的内容，将下一个位置坐标用变量x、y返回。

"寻找(x,y)的下一个位置坐标"的操作通过代码：

xx1 = x; yy1 = y; /*将坐标(x1,y1)初始化为当前访问的坐标 (x,y)，因为(x,y)不能被改动*/

flag = nextxy(x1,y1,count); /*寻找(x,y)下一个位置坐标(x1,y1)*/

while(flag == 0 count 7){ /*循环地寻找(x,y)的下一个坐标*/

countcount = count + 1;

flag = nextxy(x1,y1,count);

}

实现。程序最开始将(x1,y1)初始化为当前坐标(x,y)，因为"马"的当前位置坐标(x,y)不能被轻易改动。然后将x1、y1作为函数nextxy的参数传递，并通过参数x1和y1返回当前坐标(x,y)的第count个下一个坐标(x1,y1)。只有当flag为1时，才表明找到了下一个坐标，于是循环可以停止。但是如果count的值超过了7，则说明无法找到(x,y)的下一个坐标，也就说明棋走不通了。所谓当前位置(x,y)的"下一个位置"，如图9-8所示。

（点击查看大图）图9-8 (x,y)的"下一个位置"示意

图中实心的圆圈的坐标为(x,y)，它周围的8个空心的圆圈1～8，为当前坐标(x,y)的可选的"下一个"坐标(x1,y1)。每次调用nextxy()都可能得到这8个坐标其中的一个，当参数count为i时，返回圆圈i所处的坐标。这样就保证了不返回同一个坐标。

如果像本程序这样将字符常量X和Y都设置为8，那么程序就执行8*8的马踏棋盘。但是这样一来会非常费时，实践证明应用本程序运算出8*8的马踏棋盘的结果要花几分钟的时间。因此读者在调试程序时可以通过设置X和Y的值减小棋盘的规格，从而更快地得到结果。

本程序的运行结果如图9-9所示。

（点击查看大图）图9-9 程序9-3的运行结果

网站栏目：递归函数求棋盘路径c语言 递归函数c语言怎么用
分享地址：http://azwzsj.com/article/dossggi.html