Paint on a Wall----HDU_4012----BFS_状态压缩

【Paint on a Wall----HDU_4012----BFS_状态压缩】题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=4012

/* Author:Bob Lee 2012.9.5 =============================================== 这题的意思有一个2*n的矩形,要给这个矩形涂色 每次可以涂一个矩形的一种颜色,求最少多少步可以求出 这题在比赛的时候想到了应该是用搜索,但自己的功力不够 当场没做出来 下来看了诸多大牛的资料,自己总算是有了点体会 这个是最多只有2*8的格子,所以搜索是行得通的 首先我们要有一个策略,那就是如果涂颜色的话,尽量一次涂得大一点,这样次数就少一些 然后就是每一次选择一个位置进行扩展染色,如果在扩展的过程中 遇到了已经达到目标涂色了的,就退出,因为这已经达到目标了,再涂不就覆盖了么 每一步的所有涂得的子集就加入到队列中,这是一种情况。 对于子集的的话,要和这一步的最后进行与,逐步提取出来每一个子集 如果子集已经加入过了,则跳过。 扩展也有两种情况,分单行和双行之分。 单行的话,就左右扩展 双行的话,我们只需要考虑在第一行的时候,这样可以方便我们进行操作 因为是双行,以哪一个为第一行都是一样的。 另外还有一个就是关于判重的问题,我们可以用16位的二进制来保存,见程序flag 具体细节可以见我的程序,仔细体会体会就会有收获。*/#include #include #include #include #include using namespace std; struct node { int val; int step; }; node start; bool flag[1<<16]; //这个是用来表示是否与目标颜色一致,若是一致,则为1,否则为0 int n; char str[20]; int bfs() { queue 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<=(i/n)*n; j--)//当前往左扩展,注意这种确定上线的方式,要么是n要么是2n { if( (1<= n) continue; //如果第一行下面第一个就已经是目标色了,则直接放弃本次的扩展 if( cur.val & (1 << i+n)) continue; tmp = 0; //以双行的形式往右扩展 for(int j=i; j=0; j--) { if(((1 << j) & cur.val) || ((1<<(j+n)) & cur.val)) break; if(str[j] == str[i]) tmp |= (1<


    推荐阅读