小编Eri*_*ric的帖子

前几天我被问到" 概述用n球解决迷宫的一般算法,其目标是将所有球送到迷宫中的给定位置(迷宫没有出口) ".唯一的规则是算法必须有效(优于随机移动球)并且所有发出的命令都将影响所有球,因此一个球向北移动,如果它们没有被阻挡,所有其他球也将移动.

为此,我做了一些假设,即那些

• 迷宫是标准/完美的
• 球不能相互阻挡
• 球可以到达要求的位置
• 命令会让球滚动直到击中墙壁
• 命令只能是N/S/E/W.
• 迷宫是随机构造的,每次重置时球随机分布
• 迷宫操作员可以立即观察到所有的迷宫

并且,使我的算法工作

• 球不相同(例如,球上有数字或其他东西)
• 迷宫操作员有一个照相记忆

鉴于此,我认为最好的想法是

1. 随机(或以聪明的方式)移动球直到两个球到达目标位置
2. 保存从起始位置到结束位置的路径.
3. 确定那些球和它们来自哪里,并为每个球做1.

这个递归算法中的"中断"是当所有的球都有办法到达给定目标时(我认为是O(log(n))递归？)

这有用吗？有没有其他人有更好的算法呢？

我有另一个想法,包括将所有球移动到相同的随机位置,然后将它们全部移动为一个球,但这似乎是一个更糟糕的算法.

另一个想法是生成一个图形(图形理论),其中球的所有稳定点都是一个节点,并且移动将是一个边缘,但我看不出它是如何不需要很多蛮力待做.

TL; DR:我的代码在Java中"快速",但在C++中却很慢.为什么？

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>


using namespace std;

int read(string data, int depth, int pos, vector<long>& wantedList) {
    // 91 = [
    if (data.at(pos) == 91) {
        pos++;
        // Get first part
        pos = read(data, depth + 1, pos, wantedList);
        // Get second part
        pos = read(data, depth + 1, pos, wantedList);
    } else {
        // Get the weight
        long weight = 0;
        while (data.length() > pos && isdigit(data.at(pos))) {
            weight = 10 * weight …