每次排序二个垃圾箱

在只有4个垃圾箱的情况下，我被下列问题困住了。我可以做6或8，但不是4.另外，有人可以帮我想出一个通用的算法呢？每次排序二个垃圾箱

您有n个垃圾箱（以B A B A ...的交替顺序排列），您可以一次移动2个垃圾箱并获得2个插槽。对它们进行排序，以便最终所有“B”箱中的所有“A”箱都保留下来。它们应该都是相邻的，即最终没有差距。例如：

_ _ _ _ B A B A

感谢

编辑：是的，你必须一次移动两成相邻箱成两个相邻的斑点。

编辑2：不，你不能转置垃圾箱。这里有6个箱的例子：

_ _ _ _ _ _ BABABA

_ _ _ _ ABB _ ABA

_ _ _ _ ABBBAA _

_ AAABBB _ _ _

来源

2014-10-18 Riz

当您移动2个垃圾箱时，他们是否必须移动到相邻的位置？当你选择两个箱子移动时，你是否必须选择两个相邻的箱子？如上所述，这不是很清楚.. – 2014-10-18 18:30:32

是@MikeDinescu，我编辑了这个问题 – Riz 2014-10-18 18:34:34

当你移动2个垃圾箱时，你能移动它们吗？（也就是'__BA' =>'AB__'？当你将两个箱子移动到两个相邻的点时，这些点需要是空的吗？ – dbc 2014-10-18 18:46:09

一个简单的广度优先搜索可达位置的4箱案例表明，它实际上不能解决。下面是粗糙的伪代码，所以你可以尝试编写自己：

todo_queue = ["____BABA", []] 
path_to_position = {} 
while things in todo_queue: 
    (position, path) = todo_queue.next() 
    if position in path_to_position: 
     continue # We've been here before. 
    if position is success: 
     print path 
     EXIT HERE 
    for my move in possible_moves(position): 
     todo_queue.add([position after move, path + [move]])

对于一个通用的解决方案，只须做的6，8，10例和12个箱特殊的是广度优先搜索案例。对于任何更大的偶数数组，您可以解决其中的4个来创建解决方案的中间，然后解决8个块。然后，您可以轻松地移动并重新排列这些解决的块，并逐对解决问题。

来源

2014-10-19 18:51:07 btilly

每次排序二个垃圾箱

回答

相关问题