Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:位运算16MSIn Reply To:位运算16MS Posted by:liuqingfang at 2012-08-18 17:47:38 > #include <iostream> > using namespace std; > > int fanzhuan[16]; > int mychess; > char chess[18]; > //翻转第i个,利用了按位异或,与1异或相当于翻转,与0异或相当于不转 > int turn[16] = {0xC800,0xE400,0x7200,0x3100,0x8C80,0x4E40,0x2720,0x1310,0x08C8,0x04E4,0x0272,0x0131,0x008C,0x004E,0x0027,0x0013}; > > //我是核心部分哦~ > bool dfs(int now,int level,int last )//从last开始 > { > if(now==level)//现在已经是第level次翻转了 > { > if(mychess==0||mychess==0x00ffff) > return true; > else > return false; > }else{ > //还剩16-last个可供翻转,但是我还想要翻转level-now个 > if(16-last<level-now) > return false; > for(int i =last;i<16;i++) > { > if(fanzhuan[i])//已经翻转过了,没必要再翻转了 > continue; > > fanzhuan[i]=1;//翻转i > mychess^=turn[i]; > > if(dfs(now+1,level,i))//如果我把第i个翻转后,继续进行会成功,那么返回true。如果将来不成功,再把i转回来 > return true; > > fanzhuan[i]= 0;//既然不成功,转回来呗 > mychess^=turn[i]; > } > return false; > } > } > > int main() > { > int i=0; > //输入字符 > while(i<16) > { > cin>>chess+i; > i+=4; > } > //将字母转化为数字 > mychess =0; > for(i=0;i<16;i++) > { > if(chess[i]=='b')//b->1 > mychess |=(1<<(15-i)); > } > if(mychess!=0&&mychess!=0xffff) > { > for(i=1;i<=16;i++) > { > //选取i个翻转 > memset(fanzhuan,0,sizeof(fanzhuan)); > if(dfs(0,i,0)) > break; > } > if(i>16) > printf("Impossible\n"); > else > printf("%d\n",i); > }else > { > printf("0\n"); > } > cin>>i; > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator