| ||||||||||
| 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