Backtracking 輕松化解 Zuma Game

最近看到有不少人在討論 Zuma Game。這個遊戲很經典,也有很多人講過,例如著名的九章算法:九章算法:九章算法 | 百度面試題:祖瑪遊戲 (但他給出的解法中不能通過測試用例findMinStep('WWBBWBBWW', 'BB')下文我會詳細講)我今天主要來講講經典的 backtracking 回溯解法,順便復習一下回溯法以及怎麼優化等。

其實用回溯法搜索答案可以應用到一類問題中,我先用 Zuma Game 拋磚引玉,然後再末尾再抽象出這一類題型形式,供大傢參考。

題目

  1. 初始的行不會擁有三個及以上的連續的同色球。
  2. 行中的球的數量不會超過20,用名為"borad"的輸入字符串表示。
  3. 你擁有的球不會超過5個,用名為"hand"的輸入字符串表示。
  4. 輸入字符串都非空,而且僅包含字符 'R','Y','B','G','W'。

要求

舉例

輸入: findMinStep("WRRBBW", "RB")
輸出: -1
解釋: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW

赞(0)