获取在一个N×N的网格
问题15的所有可能的向下和右边缘的路径:
以2×2网格的左上角开始,有6个路由(无回溯)到右下角。
通过20×20网格有多少条路线?获取在一个N×N的网格
所以我在Problem 15尝试是有点bruteforcy因为我尝试由右到左,改变方向的第一个变化的前身获得所有可能的有效路径的排列。例如,当我有一个2×2的网格(查看问题15链接图形)时,我将采用的第一条路径是右 - 右 - 下 - 下,最后一个我将采用的是下 - 右 - 右 - 右,这也是我的终止标准。我将可能的有效路径添加到列表中,并使用该列表确定是否已添加有效路径。并且为了排列一条路径,我会按照我之前提到的那样做:我从数组的右边到左边(图中的箭头指向右下角),并更改其中的第一个元素下一个元素与本身不同。所以右 - 右 - 下 - 下会变成右 - 右 - 右 - 下,这显然是无效的,因为你必须有相同数量的权利和波动才能到达角落。所以我认为是从左向右进行另一个循环,根据需要更改尽可能多的元素以获得有效的路径。所以在这个例子中右 - 右 - 右 - 下变成下 - 右 - 右 - 下。
另外,我忘记的是,我不算点,我从左上角到右下角计算边缘。
所以我已经写了一些代码,但它根本不起作用。
package projecteuler;
import java.util.ArrayList;
public class Projecteuler {
public static final int GRIDSIZE = 2;
public static void main(String[] args) {
ArrayList<boolean[]> paths = new ArrayList<>();
paths.add(new boolean[GRIDSIZE * 2]);
for(int i = 0; i < GRIDSIZE; i++) {
paths.get(0)[i] = true;
paths.get(0)[GRIDSIZE * 2 - 1 - i] = false;
}
boolean[] buf = paths.get(0).clone();
printArr(buf);
boolean tmp;
while(!checkTerminate(paths)) {
while(paths.contains(buf)) {
tmp = buf[buf.length - 1];
for(int i = buf.length - 1; buf[i - 1] != tmp && 0 < i; i--) {
buf[i] = !buf[i];
for(int j = 0; checkValid(buf) && j < i; j++)
buf[j] = !buf[j];
}
}
paths.add(buf.clone());
printArr(buf);
}
System.out.println(paths.size());
}
public static boolean checkTerminate(ArrayList<boolean[]> paths) {
boolean[] endPath = new boolean[GRIDSIZE * 2];
for(int i = 0; i < GRIDSIZE; i++) {
endPath[i] = false;
endPath[GRIDSIZE * 2 - 1 - i] = true;
}
return paths.contains(endPath);
}
public static boolean checkValid(boolean[] arr) {
int countR = 0,
countL = 0;
for(int i = 0; i < arr.length; i++)
if(arr[i])
countR++;
else
countL++;
return countR == countL;
}
public static void printArr(boolean[] arr) {
for(int i = 0; i < arr.length; i++)
System.out.print(arr[i] ? "right " : "down ");
System.out.println();
}
}
它以某种方式不会改变任何地方的任何东西。
right right down down
right right down down
right right down down
right right down down ...
等都是它的输出。看来代码根本不会排列我的路径,但也不会卡在任何for循环中。我最好的猜测是我的功能标准被放置在错误的序列中
我还想到了一种回溯解决方案,就像我们两年前在学校为迷宫做的那样,但我想看看这种方法是否可行或者在重做所有内容之前。
编辑:
我会尽力尽快落实2×2格例子的图像,但欧拉计划网站正在维护的时刻。
让在正确的一步被称为R和降压被称为D.
为了从左上角到右下角上的行和m列的网格,你会到达必须正确地执行m次并下降n次。
本质上,你将不得不得到所有可能的m R和n D的安排。
例子:对于一个2×2格,字RRDD的独特排列的数量将是方法,使你可以走了,即数量。
- RRDD
- RDRD
- DRDR
- 复员
谷歌的公式计算,其由下式给出的与重复,字母排列:
N! /(r !* r !...),其中所有r的和为n。
This question关于Math SE在寻找重复字母排列计数时首先弹出,second answer在我看来更好解释。
因此,要返回计数并且甚至要返回路径,您根本不需要遍历迷宫。只需做第一个公式计算并打印第二个问题的排列。
当某些步骤离开网格时,给出路径将是唯一要求您实际遍历迷宫的情况。
UPDATE:
因为可以把重复的字母排列的公式。
下面是演示该案例的幻灯片。看看2E在产生排列时最终如何重复排列。一般而言,重复的任何字母将导致r!因为无论放在哪个字母的排列中,都可以用另一个相同的字母来替换,而不用重新排列。
这样,如果我们将总数n分开!与r!排列,我们得到了实际独特的排列。
最后,呈现出实际的努力,在发布前解决该问题的编程挑战的问题... – meowgoesthedog
问题是**很差**写的。尽管在发布堆栈溢出问题之前已经做了必要的努力,但帖子的标题和描述问题的方式是荒谬的:您不应该假定人们已经知道您正在讨论的问题。与真正问题的外部联系是不可接受的。编辑帖子并在此处将所有必要的详细信息包含在说明中,并将标题修改为真正简洁地描述真正问题的内容。 – progyammer
@meowgoesthedog谢谢你注意到我的努力,但不知何故人们仍然在低调我的帖子。也许我的方法是太愚蠢,甚至没有认真对待haha – LordScrat