好吧,我必须编写一个程序来计算一个骑士(在棋盘上)从 (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;
}
最佳答案
这里你从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
关于c - 在无限棋盘上,骑士从 xb、yb 到 xe、ye 可以走的路线数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33156421/