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

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

游戲簡(jiǎn)介

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

游戲玩法

你可以從任意一個(gè)格子刷起，刷完一格，可以移動(dòng)到和它相鄰的格子（對(duì)角相鄰也算數(shù)），但不能移動(dòng)到較遠(yuǎn)的格子（因?yàn)橛推嵛锤刹荒懿龋。?/p>

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

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

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

相對(duì)的格子：一列之中，除了指定格子之外的另一個(gè)格子。

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

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

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

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

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

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

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

中文名：Fill It

包名：com.ActiveCoreStudio.FillIt.fhp

MD5值：1878e34bcb774111953561bc845b983d