題目大意：有一個(gè)4*4的方格，每個(gè)方格中放一粒棋子，這個(gè)棋子一面是白色，一面是黑色。游戲規(guī)則為每次任選16顆中的一顆，把選中的這顆以及它四周的棋子一并反過(guò)來(lái)，當(dāng)所有的棋子都是同一個(gè)顏色朝上時(shí)，游戲就完成了。現(xiàn)在給定一個(gè)初始狀態(tài)，要求輸出能夠完成游戲所需翻轉(zhuǎn)的最小次數(shù)，如果初始狀態(tài)已經(jīng)達(dá)到要求輸出0。如果不可能完成游戲，輸出Impossible。

主要思想：

1.如果用一個(gè)4*4的數(shù)組存儲(chǔ)每一種狀態(tài)，不但存儲(chǔ)空間很大，而且在窮舉狀態(tài)時(shí)也不方便記錄。因?yàn)槊恳活w棋子都只有兩種狀態(tài)，所以可以用二進(jìn)制0和1表示每一個(gè)棋子的狀態(tài)，則棋盤(pán)的狀態(tài)就可以用一個(gè)16位的整數(shù)唯一標(biāo)識(shí)。而翻轉(zhuǎn)的操作也可以通過(guò)通過(guò)位操作來(lái)完成。顯然當(dāng)棋盤(pán)狀態(tài)id為0(全白)或65535(全黑)時(shí)，游戲結(jié)束。

2.對(duì)于棋盤(pán)的每一個(gè)狀態(tài)，都有十六種操作，首先要判斷這十六種操作之后是否有完成的情況，如果沒(méi)有，則再對(duì)這十六種操作的結(jié)果分別再進(jìn)行上述操作，顯然這里就要用到隊(duì)列來(lái)存儲(chǔ)了。而且在翻轉(zhuǎn)的過(guò)程中有可能會(huì)回到之前的某種狀態(tài)，而這種重復(fù)的狀態(tài)是不應(yīng)該再次入隊(duì)的，所以維護(hù)isVis[i]數(shù)組來(lái)判斷id==i的狀態(tài)之前是否已經(jīng)出現(xiàn)過(guò)，如果不是才將其入隊(duì)。如果游戲無(wú)法完成，狀態(tài)必定會(huì)形成循環(huán)，由于重復(fù)狀態(tài)不會(huì)再次入隊(duì)，所以最后的隊(duì)列一定會(huì)是空隊(duì)列。

3.由于0^1=1，1^1=0，所以翻轉(zhuǎn)的操作可以通過(guò)異或操作來(lái)完成，而翻轉(zhuǎn)的位置可以通過(guò)移位來(lái)確定。

# include <iostream># define N 65536using namespace std;int q[N*2];int front, rear, i, j, id = 0, tmp;bool vis[N]; //標(biāo)記狀態(tài)是否出現(xiàn)過(guò)int step[N]; //記錄到達(dá)id==i時(shí)狀態(tài)翻轉(zhuǎn)所需次數(shù)char color; int main(void){for(i = 0; i < 4; i++)for(j = 0; j < 4; j++){cin >> color; //輸入初始狀態(tài)并轉(zhuǎn)換為idid <<= 1;if(color == 'b')id++;}if(id == 0 || id == 65535){cout << 0 << endl; //如果初始狀態(tài)滿足直接輸出return 0;}q[rear++] = id; //初始狀態(tài)id入隊(duì)vis[id] = true;step[id] = 0; //到達(dá)初始狀態(tài)所需次數(shù)置0while(front < rear) //隊(duì)列不為空繼續(xù)操作 {id = q[front++]; //隊(duì)頭元素出隊(duì)for(i = 0; i < 4; i++)for(j = 0; j < 4; j++){tmp = id; //需要遍歷隊(duì)頭元素的16種操作 每次還原tmpif(i == 0)tmp ^= 1 << (11-4*i-j); //翻轉(zhuǎn)的位置為15-(4*(i+1)+j)else if(i == 3)tmp ^= 1 << (19-4*i-j); //翻轉(zhuǎn)的位置為15-(4*(i-1)+j)else{tmp ^= 1 << (11-4*i-j);tmp ^= 1 << (19-4*i-j);}if(j == 0)tmp ^= 3 << (14-4*i-j); //翻轉(zhuǎn)的位置為15-(4*i+j)、15-(4*i+j+1)else if(j == 3)tmp ^= 3 << (15-4*i-j); //翻轉(zhuǎn)的位置為15-(4*i+j-1)、15-(4*i+j)else{tmp ^= 7 << (14-4*i-j); //翻轉(zhuǎn)的位置為15-(4*i+j-1)、15-(4*i+j)、15-(4*i+j+1) }if(tmp == 0 || tmp == 65535){cout << step[id]+1 << endl;return 0;}if(!vis[tmp]) //如果是新?tīng)顟B(tài) 入隊(duì) {q[rear++] = tmp;vis[tmp] = true;step[tmp] = step[id]+1; // 當(dāng)前次數(shù)=到達(dá)隊(duì)頭元素所需次數(shù)+1 }}}cout << "Impossible" << endl;return 0;} View Code

?

后記：

第一次做狀態(tài)壓縮的題，也是現(xiàn)學(xué)現(xiàn)賣，有些像位運(yùn)算的公式什么的還是理解的不是很透徹，關(guān)于狀態(tài)壓縮的題還是需要再多做幾個(gè)。

?

轉(zhuǎn)載于:https://www.cnblogs.com/Silence-AC/p/3234199.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1753 Flip Game (黑白棋) （状态压缩+BFS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。