我需要计算从原点到点(n，0(的路径数，其中n>0和移动次数必须正好是2 * n。 我只能移动
(x + 1， y( [→]， (x， y + 1( [↑]，(x - 1， y + 1( [-]， (x + 1， y - 1( [&]， 或 (x + 1， y + 1( [%]。
限制是：
[-] 和 [&] 从不以任何顺序直接相邻。
[↑] 和 [→] 从不按任何顺序直接相邻。
[↑] 和 [%] 从不按任何顺序直接相邻。
程序需要显示所有移动(x>0 和 y>0(。 示例：对于 n = 7，(7( = 416449 我无法让它显示正确答案。
package algo;
public class Test {
static int k = 0;
public static int calcul(int x, int y, int n, int pasi, int p, int[] num) {
if (x ==n && y == 0 && pasi == 2 * n ) {
{
for(int i=1;i<=2*n;i++)
System.out.print(num[i]);
System.out.println(" ");
k = k + 1;
}
} else if (pasi < 2 * n && x >= 0 && y >= 0) {
if (num[pasi] != 2) {
num[pasi + 1] = 1;
calcul(x + 1, y, n, pasi + 1, 1, num);
}
if (num[pasi] != 1 && num[pasi] != 6) {
num[pasi + 1] = 2;
calcul(x, y + 1, n, pasi + 1, 2, num);
}
if (num[pasi] != 5) {
num[pasi + 1] = 4;
calcul(x - 1, y + 1, n, pasi + 1, 4, num);
}
if (num[pasi] != 4) {
num[pasi + 1] = 5;
calcul(x + 1, y - 1, n, pasi + 1, 5, num);
}
if (num[pasi] != 2) {
num[pasi + 1] = 6;
calcul(x + 1, y + 1, n, pasi + 1, 6, num);
}
}
return k;
}
public static void main(String[] args) {
int n = 3;
int[] num = new int[n * 2 + 1];
int q = calcul(0, 0, 2, 0, 0, num);
System.out.println("paths:" + q);
}
}
private static boolean isPossibleOrigin(int x, int y, int n, int pasi) {
return x >= 0 && y >= 0 && pasi < 2 * n && (x+y)/2<2*n-pasi;
}
public static int calcul(int x, int y, int n) {
if (x == n && y == 0 ) {
return 1;
} else if (isPossibleOrigin(x, y, n, 0)) {
return
right(x+1, y, n,1)
+ up(x, y+1, n, 1)
+ leftup(x-1, y+1, n, 1)
+ rightdown(x+1, y-1, n, 1)
+ rightup(x+1, y+1, n, 1);
}
return 0;
}
public static int right(int x, int y, int n, int pasi) {
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
right(x+1, y, n, pasi + 1)
+ leftup(x-1, y+1, n, pasi+1)
+ rightdown(x+1, y-1, n, pasi+1)
+ rightup(x+1, y+1, n,pasi+ 1);
}
return 0;
}
public static int leftup(int x, int y, int n, int pasi) {
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
right(x+1, y, n, pasi + 1)
+ leftup(x-1, y+1, n, pasi + 1)
+ up(x,y+1,n,pasi+1)
+ rightup(x+1, y+1, n,pasi+ 1);
}
return 0;
}
public static int rightup(int x, int y, int n, int pasi) {
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
right(x+1, y, n, pasi + 1)
+ leftup(x-1, y+1, n, pasi + 1)
+rightdown(x+1, y-1, n, pasi+1)
+ rightup(x+1, y+1, n,pasi+ 1);
}
return 0;
}
public static int up(int x, int y, int n, int pasi) {
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
+up(x, y+1, n, pasi+1)
+ leftup(x-1, y+1, n, pasi + 1)
+rightdown(x+1, y-1, n, pasi+1)
;
}
return 0;
}
public static int rightdown(int x, int y, int n, int pasi) {
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
right(x+1, y, n, pasi + 1)
+rightdown(x+1, y-1, n, pasi+1)
+ up(x,y+1,n,pasi+1)
+ rightup(x+1, y+1, n, pasi + 1);
}
return 0;
}
public static void main(String[] args) {
System.out.println("Paths:"+calcul(0, 0, 1));
}
我认为"？"可以替换为"(x+y(/2<2*n-pasi"，对吗？
一般来说，这些问题可以通过纯递归来解决，而不需要static变量。只需计算每个可能的延续的路径数即可。一旦在给定约束下到达所需的目的地，将完整路径的数量增加 1 (return 1;(，否则通过返回 0 来中断递归。
private static boolean isPossibleOrigin(int x, int y, int n, int pasi) {
return x >= 0 && y >= 0 && pasi < 2 * n && ?;
}
public static int calcul(int x, int y, int n) {
if (x == n && y == 0 && n == 0) {
return 1;
} else if (isPossibleOrigin(x, y, n, 0)) {
return
right(x, y, n, 1)
+ up(x, y, n, 1)
+ leftup(x, y, n, 1)
+ rightdown(x, y, n, 1)
+ rightup(x, y, n, 1);
}
return 0;
}
对于每个可能的方向，编写一个考虑到其法律延续的类似方法。
public static int right(int x, int y, int n, int pasi) {
x = x+1;
if (x == n && y == 0 && pasi == 2 * n) {
return 1;
} else if (isPossibleOrigin(x, y, n, pasi)) {
return
right(x, y, n, pasi + 1)
+ leftup(x, y, n, pasi + 1)
+ rightdown(x, y, n, pasi + 1)
+ rightup(x, y, n, pasi + 1);
}
return 0;
}
...
最后，考虑到当节点到目标的距离大于剩余移动次数时，访问节点不会导致完整的路径，您可以获得相当大的性能提升。我在现场留下了一个问号，这是您添加适当条件来检查这一点的好地方。