转载请注明出处,谢谢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;
}
分享到:
相关推荐
HDUACM201303版_10搜索入门
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
杭州电子科技大学oj平台上的第1010题,是关于搜索的题目,很不错的题
搜索 dfs 解题代码 hdu1241
有题,有解题思路,有解题代码 hdu2516、poj1067和hdu1527、hdu2177、hdu2176等等
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
acm hdu as easy as a+b
hdu2101AC代码
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
NULL 博文链接:https://128kj.iteye.com/blog/1734821
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu_2102_passed_sorce
自己做的HDU ACM已经AC的题目
hdu 1166线段树代码
HDU最全ac代码