c - 在无限棋盘上，骑士从 xb、yb 到 xe、ye 可以走的路线数

Question

好吧，我必须编写一个程序来计算一个骑士(在棋盘上)从 (xb, yb) 到 (xe, ye) 可以走的路线数。我不确定我哪里出错了。好吧，我知道计数不会添加任何东西，并且会在我的代码中保持为 0，但我也觉得我也不会太远。我只是在寻找正确方向的插入力。提前致谢

#include <stdio.h>
#include <stdlib.h>

int numRoutes(xb, yb, xe, ye, n){

  int count = 0;

  if(n>0){
      count = count + numRoutes(xb+1, yb+2, xe, ye, n-1);
      count = count + numRoutes(xb+1, yb-2, xe, ye, n-1);
      count = count + numRoutes(xb-1, yb+2, xe, ye, n-1);
      count = count + numRoutes(xb-1, yb-2, xe, ye, n-1);
      count = count + numRoutes(xb+2, yb+1, xe, ye, n-1);
      count = count + numRoutes(xb+2, yb-1, xe, ye, n-1);
      count = count + numRoutes(xb-2, yb+1, xe, ye, n-1);
      count = count + numRoutes(xb-2, yb-1, xe, ye, n-1);
  }
  return count;
}




int main(int argc, char *argv[]){

int xb, xe, yb, ye, n;

printf("Start coordinate: ");
scanf("%d %d", &xb, &yb);

printf("End coordinate: ");
scanf("%d %d", &xe, &ye);

printf("Length: ");
scanf("%d", &n);

int allRoutes = numRoutes(xb, yb, xe, ye, n);

printf("Number of routes: %d\n", allRoutes);

 return 0;   
}

Answer 1

这里你从x,y开始，想去tx,ty，最大长度为n。

在递归方法中，您的函数必须:

• 检查是否可能:你至少需要 Dx+Dy 移动(其中 Dx=ABS(x-tx)，Dy=ABS(y-ty)，如果我是对的，那么如果 n < Dx+Dy找不到路由(返回0)
• 检查您是否在目的地。如果是，你有一条路线(返回 1)
• 数量 = 0
• 对于每个可能的移动(8 个方向，x+1,y；x-1,y；x+1,y+1…)用这个新的 x,y，相同的目标和 n-1(你使用一个移动)并将结果值与数字相加
• 返回号码

如果您想知道找到了哪些路由，您必须管理一个全局堆栈并在进入时推送 (x,y)，在离开和找到目标时弹出它。此外，当您找到目标时，您应该将路线保存在某处(堆栈的内容)。

一些改进:

• 有一个 visited[N][N] 数组初始化为 0，每次 push() 时置 1，每次 pop() 时置 0。然后你可以拒绝测试这个路线仍然被访问过的位置(防止循环，圆圈......)
• 检查 x,y 以防止访问板外的元素
• 也许检查棋盘上是否存在其他东西(在其他棋子周围移动，而不是在它们“内部”移动)

它可能会查看(不阻止循环，不检查板限制，并使用 pstack() 打印堆栈内容的函数):

int routes(int x, int y, int tx, int ty, int n) {
  int nb = 0;  // number found
  int lng = ABS(x-tx)+ABS(y-ty); // minimal length to reach destination
  if (n < lng) {
    return(0);  // not possible, it will not be a route
  }
  push(x, y);
  // if we are on destination -> 1: we found a route to destination
  if ((x == tx) && (y == ty)) {
    pstack();
    pop();
    return(1);
  }
  // try each move (8 directions)
  nb += routes(x+1, y+0, tx, ty, n-1);
  nb += routes(x+1, y+1, tx, ty, n-1);
  nb += routes(x+1, y-1, tx, ty, n-1);
  nb += routes(x+0, y+1, tx, ty, n-1);
  nb += routes(x+0, y-1, tx, ty, n-1);
  nb += routes(x-1, y+1, tx, ty, n-1);
  nb += routes(x-1, y+0, tx, ty, n-1);
  nb += routes(x-1, y-1, tx, ty, n-1);
  pop();
  return(nb);
}

这将为 routes(4, 4, 5, 5, 2); 提供:

. (4,4) (5,4) (5,5) 
. (4,4) (5,5) 
. (4,4) (4,5) (5,5) 
Found 3 routes from (4,4) to (5,5) with length 2