Skip to content

Latest commit

 

History

History
 
 

488.Zuma-Game

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 
 
 

488.Zuma-Game

解法1

此题并没有太多的技巧,就是暴力的深度搜索,遍历每次取的hand ball、以及它在board中可以插入的位置,更新得到newboard和newhand,然后不停地调用DFS(newboard,newhand)即可。

可以剪枝的地方有两处:

  1. 手头的hand里面如果有若干个球是同色的话,那么只需要考察其中一个即可。也就是说,DFS的时候只遍历hand里面不同色的球。
  2. 选定了一个hand ball之后,那么它在board里插入的位置也不是随意的。显然,如果将hand ball插入board里同色的位置肯定是较优的。也就是说对于hand[i]和board的位置j,如果board[j]!=hand[i]那么就直接跳过。

解法2

跟上面的解法不同,有另外一种DFS的写法。基本框架不变,但是在分支的思路上不一样。解法1,是遍历手头的ball,再遍历所有它适合插入的位置,这是一个两层的遍历。但在下面这个更高效的解法中,我们遍历所有可以插入的位置,然后查看是否手头有足够的球能使得这个位置上产生三连消。

这样的思想依据是:对于任何一个ZUMA Game的初始board,在消除的过程中,不管情况多复杂,最后必然会引发第一个引爆点。比如说WBBRRW,第一个引爆点可能是W(WW)BBRRW,条件是你手头有两个W;也可能是WBB(B)RRW,条件是你手头有一个B;又有可能是WBBRR(R)W,条件是你手头有一个R;也有可能是W(WW)BBRRW(WW),条件还是你手头有两个W。如果相应的条件满足,这些位置都有可能是第一个引爆点。为什么只关心引爆点呢,因为你即使先做了其他操作,使得乱如WXBXXBXRRXW,最终还是会引爆的,而引爆的一个导火索,就是最初WBBRRW中的某个元素。

于是你分支去DFS,进入不同的平行时空,再考察下一个层级下的第一个引爆点...因此类推,依然是一个常规的DFS。但是效率会大大提高。

======================================================

注意下面这个case,OJ给的标准答案是错误的。很不幸,这里的解答也都是错误的。这个case太NB了,我服气,

https://leetcode.com/problems/zuma-game/discuss/254300/Right-answer-for-this-questions

Leetcode Link