|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
能否详细地解释一下马踏棋问题的求解步骤,例如定义的指针含义,所有if语句条件含义,while语句条件含义
- #include <stdio.h>
- #define X 8
- #define Y 8
- int chess[X][Y];
- // 找到下一个可走的位置
- int next(int *px, int *py, int count)
- {
- int x = *px;
- int y = *py;
- switch(count)
- {
- case 0:
- if (x+2<=X-1 && y-1>=0 && chess[x+2][y-1] == 0)
- {
- *px = x + 2;
- *py = y - 1;
- return 1;
- }
- break;
- case 1:
- if (x+2<=X-1 && y+1<=Y-1 && chess[x+2][y+1] == 0)
- {
- *px = x + 2;
- *py = y + 1;
- return 1;
- }
- break;
- case 2:
- if (x+1<=X-1 && y-2>=0 && chess[x+1][y-2] == 0)
- {
- *px = x + 1;
- *py = y - 2;
- return 1;
- }
- break;
- case 3:
- if (x+1<=X-1 && y+2<=Y-1 && chess[x+1][y+2] == 0)
- {
- *px = x + 1;
- *py = y + 2;
- return 1;
- }
- break;
- case 4:
- if (x-2>=0 && y-1>=0 && chess[x-2][y-1] == 0)
- {
- *px = x - 2;
- *py = y - 1;
- return 1;
- }
- break;
- case 5:
- if (x-2>=0 && y+1<=Y-1 && chess[x-2][y+1] == 0)
- {
- *px = x - 2;
- *py = y + 1;
- return 1;
- }
- break;
- case 6:
- if (x-1>=0 && y-2>=0 && chess[x-1][y-2] == 0)
- {
- *px = x - 1;
- *py = y - 2;
- return 1;
- }
- break;
- case 7:
- if (x-1>=0 && y+2<=Y-1 && chess[x-1][y+2] == 0)
- {
- *px = x - 1;
- *py = y + 2;
- return 1;
- }
- break;
- }
- return 0;
- }
- int setHorse(int x, int y, int tag)
- {
- int x1 = x, y1 = y, flag = 0, count = 0;
- // tag记录轨迹
- chess[x][y] = tag;
- // 如果tag等于64退出程序
- if (tag == X*Y)
- {
- return 1;
- }
- // 如果可以走,那么flag为1
- flag = next(&x1, &y1, count);
- // 否则尝试其他路径
- while (flag == 0 && count < 7)
- {
- count += 1;
- flag = next(&x1, &y1, count);
- }
- // 递归进入下一个坐标
- while (flag)
- {
- // 返回1表示成功找到落脚点
- if (setHorse(x1, y1, tag+1))
- {
- return 1;
- }
- // 否则从上一步重新尝试
- x1 = x;
- y1 = y;
- count += 1;
- flag = next(&x1, &y1, count);
- while (flag == 0 && count < 7)
- {
- count += 1;
- flag = next(&x1, &y1, count);
- }
- }
- if (flag == 0)
- {
- chess[x][y] = 0;
- }
- return 0;
- }
- int main(void)
- {
- int i, j;
- for (i = 0; i < X; i++)
- {
- for (j = 0; j < Y; j++)
- {
- chess[i][j] = 0;
- }
- }
- // 讲道理,从 (2, 0) 坐标开始计算是比较容易出结果的
- // 如果你比较有耐心,或 CPU 特别强劲,可以尝试计算其它坐标
- if (setHorse(2, 0, 1))
- {
- for (i = 0; i < X; i++)
- {
- for (j = 0; j < Y; j++)
- {
- printf("%02d ", chess[i][j]);
- }
- putchar('\n');
- }
- }
- else
- {
- printf("可惜无解!\n");
- }
- return 0;
- }
复制代码
这段代码是解决马踏棋盘问题的程序,其主要思路是通过递归的方式试图找到一条从初始位置开始覆盖所有棋盘格子的路径。下面对关键部分进行详细解释:
定义:
1. `int chess[X][Y]`:用来记录棋盘上每个位置是否被访问过的数组;
2. `int next(int *px, int *py, int count)`:用来确定马接下来应该走到哪个位置的函数;
3. `int setHorse(int x, int y, int tag)`:用来递归调用 next 函数,尝试所有的可能性,找到一条覆盖棋盘所有格子的路径,并将路径存储在 chess 数组中。
指针含义:
next 函数中传入的 px 和 py 分别表示当前马所在的位置,函数内部会根据计算出来的下一个可行位置更新 px 和 py 的值。
if 语句条件含义:
switch 语句中的 case 分支代表了八个方向,每个方向都有相应的 if 语句,其条件含义为:如果下一个可能走的位置(即棋盘上坐标为 (x+2, y-1)、(x+2, y+1)、(x+1, y-2) 等)未被访问过,则将 px 和 py 的值更新为该位置,并返回 1;否则返回 0。
while 语句条件含义:
1. 第一个 while 循环的条件为 flag == 0 && count < 7,其中 flag==0 表示当前方向上已经无法走下去了,需要尝试其他方向;count < 7 表示还有其他方向可以走(共八个方向),因此如果当前方向已经遍历完了,需要切换到下一个方向并重新尝试。
2. 第二个 while 循环的条件为 flag == 1,表示当前位置可以走,并且递归调用 setHorse 函数前往下一个位置。如果递归成功找到路径,立即返回 1;否则需要回溯到上一步,从其他方向继续尝试。
总体来说,该程序使用了深度优先搜索的思想,通过递归调用 setHorse 函数和 next 函数,不断试图寻找可行路径。当找到路径时,将其存储在 chess 数组中,最后输出即可得到一条解决马踏棋盘问题的路径。
|
|