每次排序二個垃圾箱

在只有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

每次排序二個垃圾箱

回答

相關問題