Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:位运算16MS

Posted by xiaogaga at 2013-05-07 16:26:45 on Problem 1753
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator