c - 骑士之旅- 给定 n 步，骑士在 n 步中有多少种选择可以从 (1,1) 移动到 (8,8)？

Question

我一直在努力提高我在 C 中的递归技能，并且遇到了这个问题。我试图解决它，但代码似乎无法正常工作。例如，骑士有 108 个选项可以在 6 次移动中从 (1,1) 移动到 (8,8)，而在我的代码中结果完全不同。问题是在 8x8 棋盘中，有多少种方法可以将骑士从 (1,1) 移动到 (8,8) n 步(n 由用户给出)。这是我的代码:

#include <stdio.h>
#define SIZE 8
//x,y coordinates of the knight.
int knightsTour(int x, int y, int num);
void main() {
int n;
int result;
    do {
        scanf(" %d", &n);
        result = knightsTour(1,1,n);
        printf("%d\n", result);
    } while (n > 0);
}
int knightsTour(int x,int y,int num) {
int result = 0;
int i, j;
if (num == 0) {
    return 0;
}
if (((x > 8) || (y > 8))||((x == 8) && (y == 8))) {
    return 0;
}
for (i = 1; i <= SIZE; i++) {
    for (j = 1; j <= SIZE; j++) {
        if ((i != y) && (j != x) && ((i != y + j) && (j != x + i)) && ((i != y + j) && (j != x - i))
            && ((i != y - j) && (j != x + i)) && ((i != y - j) && (j != x - i))) {
            result += knightsTour(i, j, num - 1) + 1;
        }
    }
}
return result;
}

Answer 1

您的代码有几个问题:

• 调用 recursivev 函数时，您无条件地将结果加一。您应该只计算 6 步后落在 h8 上的路径，只有在您跳到新位置后才能检查这些路径。
• 当你想找到可能的走法时，检查棋盘上的所有方 block 是一种浪费。你知道骑士的等级，所以你也知道八种可能的 Action 。你必须小心不要跳下棋盘。在函数开始时更容易验证 rank 和 file 是否有效。

一种方法是以下递归方法:

• 等级和文件有效吗？如果不是，则返回 0。
• 我们是否达到了所需的步数？如果是，则当前方格为 h8 时返回 1，否则返回 0。
• 返回骑士从当前位置开始的八步可能移动中少走一步的有效步数的总和。你不需要在这里检查，因为在函数开始时会检查着法的有效性。

综合起来:

#include <stdio.h>

#define SIZE 8

int knightsTour(int x, int y, int num)
{
    if (x < 1 || x > SIZE) return 0;
    if (y < 1 || y > SIZE) return 0;

    if (num == 0) return (x == SIZE && y == SIZE);

    return knightsTour(x + 2, y + 1, num - 1)
         + knightsTour(x + 1, y + 2, num - 1)
         + knightsTour(x - 1, y + 2, num - 1)
         + knightsTour(x - 2, y + 1, num - 1)
         + knightsTour(x - 2, y - 1, num - 1)
         + knightsTour(x - 1, y - 2, num - 1)
         + knightsTour(x + 1, y - 2, num - 1)
         + knightsTour(x + 2, y - 1, num - 1);
}

int main(void)
{
    int result = knightsTour(1, 1, 6);

    printf("%d\n", result);
    return 0;
}

这段代码很简单，它确定了 108 种可能的着法。