Fill It(刷滿油漆格子手機版)

刷滿油漆格子是一款闖關的格子刷漆手機游戲，玩家將白色涂抹成自己喜歡的顏色，那注意刷漆的順序，千萬不用遺漏一個白色格子，下面西西帶來了刷滿油漆格子游戲下載，趕緊來體驗吧。

游戲簡介

刷滿油漆格子是一款玩法非常簡單新穎的休閑游戲，你可以將白色的物體涂成你喜歡的顏色，注意千萬不要遺漏任何一個白色的哦，豐富的關卡在期待你來挑戰(zhàn)哦，快來體驗吧。

游戲玩法

你可以從任意一個格子刷起，刷完一格，可以移動到和它相鄰的格子（對角相鄰也算數(shù)），但不能移動到較遠的格子（因為油漆未干不能踩�。�

比如：a d b c e f 就是合格的刷漆順序。

c e f d a b 是另一種合適的方案。

當已知 N 時，求總的方案數(shù)。當N較大時，結(jié)果會迅速增大，

相對的格子：一列之中，除了指定格子之外的另一個格子。

1、構(gòu)造兩個動態(tài)規(guī)劃數(shù)組和一個計數(shù)器sum，一個數(shù)組a[x]，表示在2*x的格子條件下，從最邊緣一列的一個角的格子出發(fā)，遍歷全體格子的種類數(shù)，顯然a[1]=1,另一個數(shù)組b[x]，表示在2*x的格子條件下，從一個角的格子出發(fā)，遍歷全體格子后回到與之相對的格子的種類數(shù)。如圖所示，顯然因為要考慮到回來的路徑，因此除了出發(fā)點之外，每一列都只有2種選擇方法，因此b[x]=2*b[x-1]

2、先考慮出發(fā)點在角上的問題，從一個角出發(fā)，只有3種可能性，

（1）那就是先去相對的格子，然后前往下一列，這就簡化成為從2*x-1列的格子中，從一個角出發(fā)遍歷所有格子的問題，因為前往下一列的第一個格子有兩種選法，因此a[x]+=2*a[x-1];

（2）第二種可能性就是先去遍歷其余格子，最后以相對的格子收尾。此時a[x]+= b[x];

（3）第三種可能性較為復雜，先經(jīng)過第二列的一次轉(zhuǎn)折，然后到第三列的一個角上進行遍歷。此時第二列有2種選法，第三列有2種選法，因此a[x]+=4*a[x-2]; 

3、再去考慮出發(fā)點在中間的問題，如圖所示，出發(fā)點在中間的時候，顯然不能直接往下走，否則無法遍歷所有點，應當是先遍歷左邊（右邊）所有點，然后回到相對的點，然后遍歷右邊（左邊）的點。注意先遍歷的時候，必須是采用“遍歷全體格子后回到與之相對的格子”的走法，否則無法遍歷出發(fā)點正下方的點，而后遍歷則不受限制。因此設從第i列開始出發(fā)，出發(fā)點有兩種選法，第一落腳點又有兩種走法，后遍歷的第一落腳點又有兩種走法，走完總走法數(shù)為2*(2*b[i-1]*2*a[n-i])+2*(2*b[n-i]*2*a[i-1]) （加法的前一半是先遍歷左邊，后一半是先遍歷右邊） 

4、總走法數(shù)就是4*a[i]（因為有4個角）+ 從2到第n-1列所有從中間走法數(shù)的和。

中文名：Fill It

包名：com.ActiveCoreStudio.FillIt.fhp

MD5值：1878e34bcb774111953561bc845b983d