Paint on a Wall----HDU_4012----BFS_状态压缩
题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=4012
/*Author:Bob Lee2012.9.5===============================================这题的意思有一个2*n的矩形，要给这个矩形涂色每次可以涂一个矩形的一种颜色，求最少多少步可以求出这题在比赛的时候想到了应该是用搜索，但自己的功力不够当场没做出来下来看了诸多大牛的资料，自己总算是有了点体会这个是最多只有2*8的格子，所以搜索是行得通的首先我们要有一个策略，那就是如果涂颜色的话，尽量一次涂得大一点，这样次数就少一些然后就是每一次选择一个位置进行扩展染色，如果在扩展的过程中遇到了已经达到目标涂色了的，就退出，因为这已经达到目标了，再涂不就覆盖了么每一步的所有涂得的子集就加入到队列中，这是一种情况。对于子集的的话，要和这一步的最后进行与，逐步提取出来每一个子集如果子集已经加入过了，则跳过。扩展也有两种情况，分单行和双行之分。单行的话，就左右扩展双行的话，我们只需要考虑在第一行的时候，这样可以方便我们进行操作因为是双行，以哪一个为第一行都是一样的。另外还有一个就是关于判重的问题，我们可以用16位的二进制来保存，见程序flag具体细节可以见我的程序，仔细体会体会就会有收获。*/#include<iostream>#include<queue>#include<cstdio>#include<cstdlib>#include<string>using namespace std;struct node{ int val; int step;};node start;bool flag[1<<16]; //这个是用来表示是否与目标颜色一致，若是一致，则为1，否则为0int n;char str[20];int bfs(){ queue<node> q; q.push(start); memset(flag,false,sizeof(flag)); flag[0] = true; while(!q.empty()) { node cur = q.front(); q.pop(); if(cur.val == (1 << 2*n) -1) //如果当前的状况已经全部都达成了，就返回 return cur.step; node next; for(int i=0;i<2*n;i++) { next = cur; next.step++; if( (1 << i) & cur.val )//当前已经是目标色，注意这里是用二进制表示的，所以要把1左移i位，就是那个位置 continue; int tmp = 0; for(int j = i;j<(i/n+1)*n;j++) //单行向右扩展，注意这种确定上线的方式，要么是n要么是2n { if( (1<<j) & cur.val ) //当前扩展点已经是目标色了，就不必扩展了 break; if(str[j] == str[i]) //如果当前扩展点和我的源点一样，我就涂色。 tmp = tmp | (1<<j); } for(int j = i-1;j>=(i/n)*n; j--) //当前往左扩展，注意这种确定上线的方式，要么是n要么是2n { if( (1<<j) & cur.val ) //当前扩展点已经是目标色了，就不必扩展了 break; if(str[j] == str[i]) //如果当前扩展点和我的源点一样，我就涂色。 tmp = tmp | (1<<j); } //将所有的子集加进去 for(int j=tmp; j; j=tmp & (j-1)) //这种递推方式是将tmp在涂的过程中的子集一个个提取出来，结合二进制进行联想 { if(flag[cur.val | j]) //该子集已经在我的现有情况里面了则退出 continue; flag[cur.val | j] = true; next.val = (cur.val | j); q.push(next); } //下面要考虑的是双行的情况 //由于是双行的情况，我们只需要在第一行的时候考虑就行了，第二行就可以省去 if(i >= n) continue; //如果第一行下面第一个就已经是目标色了，则直接放弃本次的扩展 if( cur.val & (1 << i+n)) continue; tmp = 0; //以双行的形式往右扩展 for(int j=i;j<n;j++) { if(((1 << j) & cur.val) || ((1<<(j+n)) & cur.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) & cur.val) || ((1<<(j+n)) & cur.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)) //这种递推方式是将tmp在涂的过程中的子集一个个提取出来 { if( flag[cur.val | j]) continue; flag[cur.val | j] = true; next.val = (cur.val | j); q.push(next); } } }}int main(){ int t; int cas = 0; scanf("%d",&t); while(t--) { scanf("%d",&n); scanf("%s%s",str,str+n); start.val = 0; start.step = 0; printf("Case #%d: %d\n",++cas,bfs()); } return 0;}