HDU 4012 Paint on a Wall 搜索
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
对于2*n的矩形，每次能选择子矩形进行染色，问达到最终要求的最小步数。
每一步选择一个位置，进行扩展，将尽可能大的部分进行标记，如果遇到已经和目标颜色一样的位置，则跳出。最后把每一步的所有子集都加入到队列当中，总共最多16个方格，如果与目标颜色一样用1表示，否则为0，这样使用一个16位的二进制数便可以保存。
对于子集来说，每次减一再与便可以，这样可以每次减少一个1。
扩展包括两种情况，一种是单行的，往两边扩展。还有一种是双行的，只需要考虑上一行为中心即可，因为下一行的情况已经考虑。
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<string>using namespace std;struct Node{int val,step; //当前情况与步数}s,e,u,v;char str[20];bool flag[1<<16]; //16位二进制数表示，是否与目标颜色一致int n;int bfs(){queue<Node>que;while(!que.empty())que.pop();que.push(s);memset(flag,false,sizeof(flag));flag[0]=true;while(!que.empty()){u=que.front();que.pop();if(u.val==(1<<(2*n))-1) //所有位置全部和目标颜色一样return u.step;for(int i=0;i<2*n;i++){v=u;v.step++;if((1<<i)&u.val) continue; //当前已经为目标色int tmp=0;for(int j=i;j<(i/n+1)*n;j++){ //单行往右扩展if((1<<j)&u.val)break;if(str[j]==str[i]) tmp|=1<<j; }for(int j=i-1;j>=(i/n)*n;j--){ //单行往左扩展if((1<<j)&u.val)break;if(str[j]==str[i]) tmp|=1<<j;}for(int j=tmp;j;j=tmp&(j-1)){ //将所有子集添加if(flag[u.val|j])break;flag[u.val|j]=true;v.val=(u.val|j);que.push(v);}if(i>=n) //只需要考虑第一行，避免还要分情况考虑continue;if(u.val&(1<<(i+n)))continue;tmp=0;for(int j=i;j<n;j++){if(((1<<j)&u.val)||((1<<(j+n))&u.val))break;if(str[j]==str[i]) tmp|=(1<<j);if(str[j+n]==str[i]) tmp|=(1<<(j+n));}for(int j=i-1;j>=0;j--){if(((1<<j)&u.val)||((1<<(j+n))&u.val))break;if(str[j]==str[i]) tmp|=(1<<j);if(str[j+n]==str[i]) tmp|=(1<<(j+n));}for(int j=tmp;j;j=tmp&(j-1)){if(flag[u.val|j])continue;flag[u.val|j]=true;v.val=(u.val|j);que.push(v);}}}}int main(){int t,cas=0;scanf("%d",&t);while(t--){scanf("%d",&n);scanf("%s%s",str,str+n);s.val=s.step=0;printf("Case #%d: %d\n",++cas,bfs());}return 0;}