首页 > 代码库 > Paint on a Wall
Paint on a Wall
Paint on a Wall
题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=4012
搜索+状态压缩
这题刚开始以为是dp（之前写过墙是一行的题，然而是在艾神讲完之后才调出来的= =），但是想不出来怎么搞，看到n<=8数据量这么小，应该搜索可以解，然后想都没想就上去写了IDA*，结果有段代码怎么都找不到bug，一直WA。
结束后，用bfs写了遍，每次转移数最多是（2n）^2，最差的情况是2n层，所以复杂度是（2n）^（4n），然而状态去重后，状态数最多为2^（2n）种，复杂度为[（2n）^2]*[2^（2n）]，由于n很小，所以不会超时。然而如果用之前的IDA*，差不多会把深度小于deep的所有解空间遍历，一定会超时。
debug用了好几个小时，最后发现是
(lower&bit[other*n+i])>0写成了
(lower&bit[other*n+i])==1...不想说什么什么了...
代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define met(a,b) memset(a,b,sizeof(a)) 5 #define mkp(state,deep) make_pair(state,deep) 6 #define X first 7 #define Y second 8 #define N 8 9 using namespace std;10 typedef pair<int,int> P;11 int T,n,ans,before,after;12 char mp[2][N+1];13 bool state[1<<16];14 int bit[20];15 void init(){16 for(int i=0;i<=16;++i)17 bit[i]=(1<<i);18 }19 void bfs(){20 int finish=(1<<(2*n))-1;21 met(state,0);22 queue<P>q;23 q.push(mkp(0,0));24 state[0]=1;25 while(!q.empty()){26 P s=q.front();q.pop();27 if(s.X==finish){28 ans=s.Y;29 return;30 }31 for(int c=0;c<n;++c)32 for(int r=0;r<2;++r)33 if((s.X&bit[r*n+c])==0){34 char color=mp[r][c];35 int other=(int)(!r);36 int upper=s.X;37 int lower=s.X;38 int deep=s.Y;39 for(int i=c;i<n;++i){40 if((upper&bit[r*n+i])>0&&mp[r][i]!=color)41 upper^=bit[r*n+i];42 else if((upper&bit[r*n+i])==0&&mp[r][i]==color)43 upper|=bit[r*n+i];44 if((lower&bit[other*n+i])>0&&mp[other][i]!=color)45 lower^=bit[other*n+i];46 else if((lower&bit[other*n+i])==0&&mp[other][i]==color)47 lower|=bit[other*n+i];48 if(!state[upper]){49 state[upper]=1;50 q.push(mkp(upper,deep+1));51 }52 int temp;53 if(r==0)temp=(before&upper)|(after&lower);54 else if(r==1)temp=(after&upper)|(before&lower);55 if(!state[temp]){56 state[temp]=1;57 q.push(mkp(temp,deep+1));58 }59 }60 }61 }62 }63 int main(void){64 init();65 scanf("%d",&T);66 for(int t=1;t<=T;++t){67 scanf("%d\n",&n);68 before=after=0;69 for(int i=0;i<2*n;++i){70 if(i<n)before|=(1<<i);71 else after|=(1<<i);72 }73 for(int i=0;i<2;++i)74 scanf("%s",mp[i]);75 bfs();76 printf("Case #%d: ",t);77 printf("%d\n",ans);78 }79 }
Paint on a Wall
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。