algorithm - 奶油沼泽拼图中的小 Sprite

Question

(感谢 Rich Bradshaw)

我正在为以下难题寻找最佳策略。

作为新的 Sprite 王，绘制王国的奶油沼泽是你的职责。
沼泽笼罩在空灵的薄雾中，到处都是奶油冻岛。
您可以让您的小 Sprite 穿过沼泽地，并在每个点指示它们飞低或飞高。
如果小 Sprite 俯冲到蛋羹上，它会分心，不会完成它的序列。由于雾气很浓，您所知道的就是小 Sprite 是否到达了另一边。

在编码方面..

bool flutter( bool[size] swoop_map ); 

这会返回一个小 Sprite 是否因给定的俯冲序列而退出。

最简单的方法是仅一次传递序列。这揭示了“大小”尝试中的所有奶油冻岛。
我宁愿选择与蛋羹数量成正比的东西 - 但在序列方面存在问题，例如:

     C......C     (that is, custards at beginning and end) 

也欢迎链接到此拼图的其他形式。

Answer 1

这让我想到了分而治之。可能是这样的(这是稍微损坏的伪代码。它可能有栅栏错误等):

retval[size] check()
{
   bool[size] retval = ALLFALSE;
   bool[size] flut1 = ALLFALSE;
   bool[size] flut2 = ALLFALSE;
   for (int i = 0; i < size/2; ++i) flut1[i] = TRUE;
   for (int i = size/2; i < size; ++i) flut2[i] = TRUE;
   if (flutter(flut1)) retval[0..size/2] = <recurse>check
   if (flutter(flut2)) retval[size/2..size] = <recurse>check
}

用简单的英语来说，它在蛋奶糊贴图的每一半上都称为颤振。如果任何一半返回 false，则整个一半都没有奶油冻。否则，一半的一半递归地应用算法。我不确定是否可以做得更好。但是，如果沼泽主要是奶油冻，则此算法有点蹩脚。

想法二:

int itsize = 1
bool[size] retval = ALLFALSE;
for (int pos = 0; pos < size;)
{
    bool[size] nextval = ALLFALSE;
    for (int pos2 = pos; pos2 < pos + size && pos2 < size; ++pos2) nextval[pos2] = true;
    bool flut = flutter(nextval)
    if (!flut || itsize == 1)
    {
        for (int pos2 = pos; pos2 < pos + size && pos2 < size; ++pos2) retval[pos2] = flut;
        pos+=itsize;
    }
    if (flut) itsize = 1;
    if (!flut) itsize*=2;
}

用简单的英语来说，它会在蛋奶糊图的每个元素上调用 flutter，一次调用一个。如果它没有找到 custard，下一次调用的元素数量将是上一次调用的两倍。这有点像二分查找，只是在一个方向上，因为它不知道要查找多少项目。我不知道这有多有效。