轉載標記處：http://blog.csdn.net/kalilili/article/details/43560257

思路：每次涂色以后必有一個格子的顏色是最終的顏色，否則這次涂色根本沒意義，所以我們把每次涂色后哪些格子成為最終顏色的所有可能都入隊，入隊的元素是一個struct包含步數和最終顏色已確定的木塊集合，這個集合必須用整數表示，所以用到狀態壓縮，因為最多只有16個格子，所以用16位的二進制來表示，1，表示此格子已是最終顏色，0，表示仍待涂色。

這道題目確實很難想，我最開始想的是用字符串哈希把每次涂的情況存下來，結果掛了。。。其實這樣的做法并不能保證就一定是最少的步驟，因為涂的情況不同，但最終都能夠到達最終的狀態。。所以并不見得就一定是最優的。。

這題至少讓我知道了如何找位壓縮后的子集。。。詳見代碼

#include<cstdio> #include<iostream> #include<cstring> #include<queue> using namespace std;struct node {int step,cur; }; int len; bool flag[1<<16]; // 記錄哪些格子已是最終顏色 char str[20];int bfs() {memset(flag,0,sizeof(flag));queue<node> que;node start={0,0};que.push(start);flag[0]=true;while(!que.empty()){node now=que.front();que.pop();if(now.cur==(1<<2*len)-1) return now.step; //顏色已涂滿所有格子node next;next.step=now.step + 1;for(int i = 0;i < 2*len; i++){ //遍歷這個圖，找個起點開始涂色int tmp=0;if((1<<i) & now.cur) continue; //這個點已是最終顏色，continuefor(int j = i;j < (i/len+1)*len; j++){ //單行向右擴展，上界的確定是技巧if((1<<j)&now.cur) break; //已擴展到最終顏色，不能把它覆蓋，擴展結束if(str[j]==str[i]) tmp|=(1<<j); //如果拓展的位置需涂的顏色和起點顏色一樣，那么就涂}for(int j = i-1;j >= (i/len)*len; j--){ //單行向左擴展，下界的確定是技巧if((1<<j) & now.cur) break; //已擴展到最終顏色，不能把它覆蓋，擴展結束if(str[j] == str[i]) tmp|=(1<<j);//如果拓展的位置需涂的顏色和起點顏色一樣，那么就涂}for(int j = tmp; j > 0; j = tmp & (j-1)){ //把本次單行擴展的所有格子最終哪些格子成為最終顏色的所有可能入隊，所有//可能也就是子集的所有可能,這種遍歷集合子集的方式屬于位壓縮的知識if(!flag[j|now.cur]){ //這種情況已經產生過就不需入隊了flag[j|now.cur]=1;next.cur=(j|now.cur); que.push(next);}}if(i >= len) continue; //雙行擴展，只要對某一行的點遍歷作為起點即可if((1<<(i+len)) & now.cur) continue; //易錯，這個起點的另一行對應的起點如果已是最終顏色，continuetmp=0; for(int j = i;j < len; j++){ //和單行拓展類似if((1<<j) & now.cur)break;if((1<<(j+len)) & now.cur)break;if(str[j] == str[i]) tmp|=(1<<j);if(str[j+len] == str[i]) tmp|=(1<<(j+len));}for(int j = i-1; j >= 0; j--){if((1<<j) & now.cur) break;if((1<<(j+len)) & now.cur) break;if(str[j] == str[i]) tmp|=(1<<j);if(str[j+len] == str[i]) tmp|=(1<<(j+len));}for(int j = tmp; j > 0; j = tmp & (j-1)){ //和單行拓展子集入隊類似if(!flag[j|now.cur]){flag[j|now.cur]=1;next.cur=(j|now.cur);que.push(next);}}}} } int main() {int t,cas = 1;scanf("%d",&t);while(t--){scanf("%d",&len);scanf("%s%s",str,str+len);printf("Case #%d: %d\n",cas++,bfs());}return 0; }

總結

以上是生活随笔為你收集整理的hdu 4012（bfs+位压缩）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。